從零開始進入動態規劃的世界（三）- 在迷宮中掌握前後順序
延續前兩篇，我們又要稍微再更進階一點點了，雖然仍然算不上難題，但帶出了更多的細節，讓我們繼續用它，來過展核心基礎知識。
都到第三篇了，我就不再囉唆，直接放上原題目英文敘述了。
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
那，我第一個問題要問什麼？應該猜的到了
對，就是狀態函數是什麼？或說，我們最終的查詢表大概長什麼樣子？
試著先想一下吧
公佈答案囉！記得上一篇說的嗎？通常簡單問題，給的輸入就是 key，要的答案就是 value，所以顯然
- Key: Given the two integers
mandn - Value: Return the number of possible unique paths
由於有兩個參數，而且是 integer，所以可以用一個 Double Array 來紀錄，至於 row 跟 col，哪個是 n，哪個是 m 要特別看仔細，有時候定義會反過來，以這題來說，定義是
- row 的總數 = m
- col 的總數 = n
最終表會長下面這樣
現在來寫點程式，先一樣寫個空殼出來吧！
def uniquePaths(self, m: int, n: int) -> int:
# 初始化一個 (m + 1) * (n + 1) 的矩陣
dp = [[0 for col in range(n + 1)] for row in range(m + 1)]
# ... 初始值，較為複雜，之後再想
# 開始動態規劃計算
for row in range(1, m + 1):
for col in range(1, n + 1):
# 這邊你會經由狀態轉移，逐步把矩陣中每個位置的答案都找到
return dp[m][n] # 回傳最右下角的位置的答案是不是很簡單？只要好好搞清楚 n, m 的定義就行。如果有細心的讀者，會注意到一個小地方，是我們初始化陣列的時候，很喜歡 + 1，因為我希望最後的答案直接就是 dp[m][n]。但也有人會偏向不要＋1，最後回傳 dp[m-1][n-1]，這些屬於個人習慣上的差異，但我覺得用 dp[m][n] 會讓你在初始化的時候更方便一些，因為有個用不到的 index 0 位置，往往可以拿來做點事情，我們等等就會看到它的價值了。
[Python 語法小教室] 另外，由於目標讀者是初學者，所以讓我額外提醒一個關於 Python 特有的小細節，請千萬不要用 [[0] * n] * m 的方式開矩陣，由於 [] * k 的這種寫法會把物件視為相同記憶體位置，你改一個地方的值，會同時改到其他地方。可以試試以下程式碼就會發現問題。
Python 3.8.5
>>> m = 3
>>> n = 2
>>> dp = [[0] * n] * m
>>> dp # [[0, 0], [0, 0], [0, 0]]
>>> dp[1][1] = 7
>>> dp # [[0, 7], [0, 7], [0, 7]]當然，以下這種寫法是安全的
dp = [[0] * n for i in range(m)]但，如果你對 Python 的運作機制不那麼熟悉，無法立刻解釋出為什麼這樣就可以，我建議就老實的用以下寫法，會大大降低你的出錯率。
dp = [[0 for j in range(n)] for i in range(m)]好，Python 特別的小細節說完了，讓我們回到原本的題目。
現在狀態的定義有了，接著呢？尋找狀態轉移對吧！這個思路應該要很直覺了，那轉移怎麼寫？如果還是沒想法，一樣，我們隨便選一個位置思考看看
假設我們現在想知道的是 row = 3、col = 3 的那格位置的答案（上方紅框框），另外，假設所有比較前面（上圖 v1 ~ v8）的答案我都已經先知道了，能不能靠他們，幫我得到紅框框那格的答案？
如果有讀者在這稍微皺了一下眉頭，想問只有 v1~v8 算是前面嗎？精確來說前、後是怎麼定義的？恭喜你，你的直覺很敏銳，這件事確實沒這麼單純，但現在讓我先簡單混過去，先當作 row 與 col 兩個 index 相同或較小的左上方區域就是前面。在之後我們會繼續回來深入探討這個問題。
好，跟上一篇爬樓梯的問題一樣，我們想想，有哪些方法可以走到這格位置？由於我們只能往右，或往下走。所以，能到這一格的上一步，只有可能是上面，或左邊。如下圖。
然後這兩種走法，一定是不會重複到的，理由跟前篇爬樓梯是一樣的，因為我被規定只能往右或往下的關係，我只要走到 v6 就不可能再走到 v8 了，反之亦然。如此，紅框框這格的“可能走法”，就可以當作是兩個藍框框的“可能走法”相加。我們得到以下的關係：
? = v6 + v8
利用這個觀察，我們把它寫成一般化，可以看出公式應該是
dp[row][col] = dp[row-1][col] + dp[row][col-1]如此，轉移式我們拿到手了，可以填空上去了
def uniquePaths(self, m: int, n: int) -> int:
# 一個 (m + 1) * (n + 1) 的矩陣
dp = [[0 for col in range(n+1)] for row in range(m + 1)]
# ... 初始值，較為複雜，之後再想
# 開始動態規劃計算
for row in range(1, m+1):
for col in range(1, n+1):
dp[row][col] = dp[row-1][col] + dp[row][col-1] # 狀態轉移公式
return dp[m][n] # 回傳最右下角的位置的答案最後，我們要來處理這題真正的大魔王，也就是如何初始化。之前的初始化都很簡單，所以感受不出來這件事的複雜性，但這一題，這邊稍微需要費點力氣研究了。
初始化的關鍵，在於狀態轉移公式。回想一下費氏數列，由於他 dp[x] 的狀態轉公式內包含了 dp[x-1] 與 dp[x-2] 的資訊，所以你最少要先有兩個數字，才有辦法啟動。
而現在 dp[i][j] 的狀態轉移公式需要的東西包含了 dp[i-1][j] 跟 dp[i][j-1]。所以，你可以想像，對於任何一個位置，你需要左邊跟上面的資訊，才有辦法往下走。下面兩張圖，分別描述不同情境，你需要“最少先知道”的部分，也就是我們的初始值。
這邊一樣提供幾種想法，看讀者覺得哪個做法更舒服。
想法1
如果我只能往右，或往下走，那最上面那一排，也就是 row index = 1 的，跟最左邊那一排，也就是 col index = 1 的，其實整排都只會有 1 種走法，就是一直不斷往右、往右、往右，或一直不斷往下、往下、往下。如此，我很快可以先把以下的值放進去，這樣就初始化完了。
def uniquePaths(self, m: int, n: int) -> int:
# 一個 (m + 1) * (n + 1) 的矩陣
dp = [[0 for col in range(n+1)] for row in range(m + 1)]
# 初始化，把最上邊跟最左邊兩排都填上 1
for row in range(1, m+1):
dp[row][1] = 1
for col in range(1, n+1):
dp[1][col] = 1
# 注意！這邊我們不管 row 還是 col，都從 2 開始！因為 1 已經初始化完了
for row in range(2, m+1):
for col in range(2, n+1):
dp[row][col] = dp[row-1][col] + dp[row][col-1] # 狀態轉移公式
return dp[m][n] # 回傳最右下角的位置的答案注意，這種初始化方式，雖然思考起來較為簡單，但因為 hardcode 的東西比較多，所以都要仔細檢查一下邊界條件，確保輸入的資料很小的時候，例如給你一個 n=1, m=1 的矩陣，甚至給你 n=0, m=0 時，會不會出錯。
想法2
還有個比較漂亮的寫法，其實我們可以巧妙的利用 index = 0 的部分，來偷做一些事情。由於我們真正在計算的只有 row 從 1~m， col 從 1~n 的部分。至於 index = 0 的地方，不管 row 還是 col 都沒用到，那如果我好好給值，就可以讓後面順利進行下去，但該怎麼給呢？
全部給 0 是很直觀的想法，因為我起始點在 row = 1, col = 1，至於 0 的地方根本不可能走到，那當然是 0 種走法。但你會發現，如果這樣給，你後面算下去會變成全部都是 0。
所以，這方法行不通嗎？其實不然，我們偷偷修改一個小地方，就可以讓他變成正確的了，如下，我們偷偷在 dp[1][0] 或 dp[0][1] 任選一個位置，把他變成 1 看看。
你會發現很神奇的，我們在 row = 1 或 col = 1 的這兩排，算出來都會是 1，也就是我們想要的結果，那之後繼續往下也一定都是對的。如果用這方法，程式碼將會更簡單，如下
def uniquePaths(self, m: int, n: int) -> int:
# 開一個 (m + 1) * (n + 1) 的矩陣
dp = [[0 for col in range(n+1)] for row in range(m + 1)]
# 初始化，把這個位置偷偷改 1 即可
dp[0][1] = 1
# 注意！這邊我們不管 row 還是 col，都能從 1 開始了
for row in range(1, m+1):
for col in range(1, n+1):
dp[row][col] = dp[row-1][col] + dp[row][col-1] # 狀態轉移公式
return dp[m][n] # 回傳最右下角的位置的答案這樣我們需要 hardcode 的東西可以降低到最少，也減少在 n 跟 m 很小的時候會發生錯誤的機率，但代價就是，這個想法比較不那麼直觀，對於那個 dp[0][1] 的定義是我們自己強加上去的，並非自然的產物，需要你真的很清楚自己在做什麼。
想法3
上面這個真的太不舒服的話，也有個折衷的辦法，就是我們只把 dp[1][1] 設為 1，這應該很好理解，就是起點，當然就是一種走法（等等，起點到底要算 0 還是 1？以這邊來說是 1）。但若這樣做，要很小心的是你的兩個迴圈依然都必須從 1 起始，那你的初始化步驟就得放在迴圈裡面，不然會被洗掉。
def uniquePaths(self, m: int, n: int) -> int:
# 開一個 (m + 1) * (n + 1) 的矩陣
dp = [[0 for col in range(n+1)] for row in range(m + 1)]
# index 都從 1 開始
for row in range(1, m+1):
for col in range(1, n+1):
if row == 1 and col == 1: # 要改在這邊初始化，否則會被洗掉
dp[row][col] = 1
else:
dp[row][col] = dp[row-1][col] + dp[row][col-1] # 狀態轉移公式
return dp[m][n] # 回傳最右下角的位置的答案以上三個想法，你喜歡哪個呢？單純以這題來說，我自己認為，老實的把第一行與第一列全部設成 1，並不是太難寫，所以我會推薦這樣做最單純。但當未來題目變得更複雜，有時候真的會覺得初始化寫起來有夠囉唆，這時候也會想是不是有更聰明的其他做法。這邊只能說每個人的取捨不同，只能依據習慣跟經驗隨機應變，但不管選那個都沒問題。
決定前後順序的關鍵
到這邊算是告一段落，但讓我們回頭探討一下，之前提到的關於”到底怎麼定義前面”的小問題，為什麼我們只取 v1 ~ v8 呢？
重新看一下這張圖，如果從題目的定義上來看，可以這樣想，因為我一定只能“往右”跟“往下”，所以我如果走到超出了 v1 ~ v8 這幾個選項以外的任何地方，就不可能再次走到紅框框上面去了，所以我在思考紅框框時，他的”前面”只可能是我圖上畫的這些。
但這個條件，有跟你迴圈跑的順序一致嗎？
讓我們回頭來看看，依照 for loop 的順序如以下：
for row in range(1, m+1):
for col in range(1, n+1):
...不管是 row 還是 col，都是照著 1,2,3, … 的順序來的。所以當你走到例如 dp[3][3] 的位置時，事實上，所有
- dp[1][1], dp[1][2], … , dp[1][n]
- dp[2][1], dp[2][2], … , dp[2][n]
- dp[3][1], dp[3][2]
都已經被走過了，也就是說，答案應該已經被算出來且記錄在查詢表上了，這個範圍如以下藍色框框：
這些全都是”前面”，而你想要的 v1~v8 也確實在裡面了，不僅如此，還多包含了右上角 … 部分的資訊。所以這樣的迴圈順序是可以的，因為他包含了所有你要的資訊，至於多的也不影響你。
但如果我今天要的”前面”順序不是這樣，而是要求往上或往左走，那前面也有可能變成是右下角，或如果我要求更奇怪的走法，那甚至可能是奇怪的歪斜的區間，這時候你的 for loop 就得依照狀況改變順序，而不能總是傻傻地 index 從小到大過一輪。
迴圈的順序是要依據情況調整的！
更嚴格來說，如果真的要完全符合題目要的順序，我們應該用 BFS（廣度優先搜尋）的方式去走才對，是因為這題剛好用最單純的兩層迴圈的順序走也不會出問題，所以可以這樣做，這個關鍵處必須徹底釐清。
到此為止，這題的所有細節，終於算是全數講到了！
如果你目前為止覺得都有看懂，最好的方法就是，拿一些類似的題目試試看，以下我放兩個類似的例子，非常建議讀者試著完全自己做做看
障礙迷宮
基本跟上面一樣，但這次中間多了一些障礙物，用一個 double array `obstacleGrid` 告訴你他們的位置，這些位置不可踏入，那該怎麼辦呢？
其實大致上跟前面幾乎一樣，應該不用贅述太多，唯一的新問題只有一個：
狀態轉移公式該怎麼改？
先想想看吧！
公佈答案囉，其實也沒有很難，只是它現在是個有”分支條件”的狀況，會依據其他參數 obstacleGrid 的值，而有不同結果。
知道這個，剩下的應該寫得出來了吧！不要等待，立刻練習看看，是讓你驗證自己是否有看懂的最佳方式。我就不放程式碼了，相信讀者一定能自己完成。
如果你真的有動手做，應該會體會到，之前提到的幾種初始化方式，會帶來什麼樣的不同。你會發現這時候用第二種初始化方式，幾乎完全不用動，但用第一種則會變得更加囉唆，至於第三種則要小心一下障礙物在哪。那該選哪一種？一樣沒有標準答案，每個人還是可以自己決定。這邊只是想讓讀者知道，這些細微差異，體現在不同題目上會是什麼感覺。
得分迷宮
最後，我們再變化一下，同樣走迷宮的例子
但現在改成先給你一個分數地圖 scores，每一個位置 scores[i][j] 有一個分數，如下
然後其餘條件幾乎一樣，你會從最左上開始，要走到最右下，每次只能往右或是往下走，差別只在，你每走到一格，就可以多獲得那一格的分數，而我要問你最高可能分數是多少。以上圖的例子來說，這個路徑走到座標 (3, 2) 的位置時，目前的得分就是 90 + 3 + 15 + 10 = 118。
現在請你用動態規劃解決他
停下來，先想想！！
好，公佈答案了囉，我只講轉移公式應該就夠了對吧？這次轉移公式就是
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + scores[i][j]由於我一路上紀錄的都是”走到這一格有可能獲得的最大分數”，然後我又只可能從上面或左邊兩個方向來，所以我只要先知道了這兩個位置的”最大可能分數”，那我就選比較大的那個，並加上這一格可以拿到的分數，就會是“走到這一格的最大可能分數”了！
剩下的我相信讀者已經有能力補完了。但這題，主要是要讓大家看一下，狀態轉移方程，不一定只有加減乘除，也時常會包含這種 Aggregate function，也就是 sum, max, min 這些，然後也可能同時出現分支判斷。所以動態規劃的題目，也很常會是問你最大、最小、最高分、可能總數、…等等，可以視為一種暗示，但當然這不是絕對的，要不要用還是取決於我們這幾篇聊的東西。
結語
這篇到這邊真的結束了！
這次的題目雖然稍難了一些，但還不到太過分。因此這邊的重點，就是要求自己要扎扎實實的把
- 狀態轉移公式寫出來
- 初始化想清楚
這些基礎打底很重要，如果你只是覺得好像有看懂，但到現在都還沒開始動手寫程式的話，我強烈建議你先停一停，好好動手把這篇跟前一篇的題目做出來（最好是不看我的寫法，自己寫出來）。
因為，等到下一篇開始，我們要開始面對轉移函示變的混亂的情況了！
