演算法練習: 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個的機率和)。 目前省去了超過凹洞後的計算，複雜度的瓶頸變成是如何取得 ✖︎ 處和▲處的機率。 因為是矩陣，直覺有想到 ✖︎ 處和▲處的計算會是對稱
