演算法練習: Kick Start 2020 Round B Wandering Robot

最近在練習用推導的方式來解演算法問題，在寫4月的Kick Start題目時，遇到一題推導的思路還可以，嘗試把過程整理起來，讓自己能更習慣。


題目連結：
https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d8565

簡單描述一下：
有一塊大小 n * m 場地，每一格是 1 * 1 (像七龍珠天下第一武道會的那種石製平台，但長寬可以不同)，中間有一個 a * b 的凹洞 (中間的石頭被移掉了)。

你有一個邏輯很簡單的機器人，只會往右或下走，可能性各一半，如果它從左上角出發，那成功到達右下角的機率是多少？

思路1：
時間複雜度： O(n * m)
空間複雜度： O(n * m)

最一開始跳出來的想法，就是依照題目的描述去模擬從左上走到右下，算機率是多少。會需要一個 n * m 的矩陣來紀錄走到每一格的幾率，並需要用2個for迴圈(巢狀)來走過每ㄧ格。

這樣可以滿足第一部分需求，但在第二部分測試的時候，不管是在空間和還是時間上，都沒辦法通過。

程式碼：


所以開始來做優化，主要是從兩個方向來看：有沒有做重複的事，有沒有做多餘的事。


思路2：
時間複雜度： O(max(n,  m))
空間複雜度： O(max(n,  m))

從多餘的事來想，因為機器人只能往右和往下走，要掉到凹洞裡，只能從上或左兩個方向，也就是說，當機器人走過凹洞後，就不會再掉進去了。

所以到達終點的機率，會等於 ✖︎ 及 ▲ 處幾率的和，後面到終點的運算都會是多餘的。

因為擔心上面的想法不夠全面，所以把凹洞的位置及形狀做改變，看想法是否還適用。

可以發現，想法還是適用，但要做一點修改，則變成是“所有” ✖︎ 及▲處幾率的和。

另外，再思考的過程，也發現了一件事，因為越過凹洞後，到達終點的機率就不會改變，在凹洞下方或右方增減大小，都不會改變最後的結果 (比較上下圖，最上面的▲處的機率是不變的，第2個▲處機率則為下面的2個的機率和)。

目前省去了超過凹洞後的計算，複雜度的瓶頸變成是如何取得 ✖︎ 處和▲處的機率。

因為是矩陣，直覺有想到 ✖︎ 處和▲處的計算會是對稱的，但沒有進一步的想法，只好實際把每一格的機率算出來，看有沒有其他想法。

在填機率的過程，發現了很熟悉的數組，1 2 1 、1 3 3 1、1 4 6 4 1，巴斯卡三角形。

所以問題變成了找到巴斯卡三角形第 k 列前 l 個的和。

程式碼：


雖然解決了複雜度的問題，但在寫Kick Start的當下沒有能通過第二部分的測試，因為上面的程式碼直接除以2ⁿ來計算機率，但當n很大時，會因為浮點數的精度遇到問題。解法是在計算過程中對機率取對數，在最後再取指數來還原成實際的機率值 (這部分的程式碼，會再補上)。