DP動態規劃 深入淺出 以Unique Path 路徑總數 為例_精選75題
如同這個Dynamic programming 深入淺出系列的開始，在經過比較簡單的入門題(Coin Change)之後，來看比較進階的二維DP題目Unique Path
學而時習之不亦樂乎，再次強調DP的解題框架，鞏固知識點。
Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。
Dynamic programming的解題框架可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
題目敘述
題目給定我們一個棋盤的高與寬，起點固定在左上角，終點固定在右下角。
每一步只能選擇往右走一格，或者往下走一格，不能回頭。
要求我們求出從起點到終點有幾條路徑。
對應的解題影片，搭配服用，效果更佳。
測試範例
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
老樣子，先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。
1.定義DP狀態 [我在哪裡]
通常遇到這種棋盤式或者帶有點座標的題目，定義一個二維狀態的DP是一種很常見且直觀的選擇。
這裡，我們可以定義DP[x, y] 為從起點(0,0)到座標(x,y)的路徑數目(方法數)。
那麼，最後我們要計算的就是DP[終點x座標, 終點y座標] = DP[ n-1, m-1]
2.推導DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]
不難發現，除了最上面的那一條row，和最左的那一條column之外，
中間的點座標都有兩種選擇(往右或往下)，反過來說，
中間的點座標可以從上面走過來，或者從左邊走過來。
所以，推廣到一般化的通式，對點座標(x, y)而言
DP[ x, y]
= 從起點左上角(0, 0)到點座標(x, y)的方法數
= 從起點左上角(0, 0)到點座標(x-1, y)的方法數 + 從起點左上角(0, 0)到點座標(x, y-1)的方法數
= DP[x-1, y] + DP[x, y-1]
3. 釐清DP初始狀態(終止條件)
[第一步怎麼走，怎麼出發的]
有幾個情況是初始條件，或稱為遞迴的終止條件。
當點座標為(0, 0)起點時，顯然，方法只有一種
DP(0, 0) = 1
另外，當點座標為最上方那條橫排時(x, 0)，方法也只有一種(因為只能從左邊走過來，沒有別的方法)
DP[x, 0] = 1
同理，當點座標為最左邊那條直排時(0, y)，方法也只有一種(因為只能從上面走下來，沒有別的方法)
DP[0, y] = 1
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
Top down DP程式碼
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# -----------------------------------
# key: (m, n) size of grid
# value: total path count from source to destinaion
memo = {}
def path_count(x, y):
if (x, y) in memo:
# look-up in memo
return memo[(x, y)]
if (x == 0) or (y == 0):
# base case (starting point) and
# special cases (top-most row as well as left-most column)
memo[(m, n)] = 1
return 1
# general case
memo[(x, y)] = path_count(x-1, y) + path_count(x, y-1)
return memo[(x, y)]
# -----------------------------------
return path_count(x=n-1, y=m-1)
複雜度分析
時間複雜度: O( m * n )
O( m * n )，板子上的每個格子點都拜訪一次。
空間複雜度: O( m * n )
O( m * n )，板子上總共有O(m * n)個格子點，也是DP table的大小。
Bottom up DP程式碼
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
rows, cols = m, n
path_dp = [ [ 1 for j in range(cols)] for i in range(rows) ]
# Dynamic Programming relation:
# Base case:
# DP(0, j) = 1 , only reachable from one step left
# DP(i, 0) = 1 , only reachable from one step up
# General case:
# DP(i,j) = number of path reach to (i, j)
# = number of path reach to one step left + number of path reach to one step up
# = number of path reach to (i, j-1) + number of path to (i-1, j)
# = DP(i, j-1) + DP(i-1, j)
for i in range(1, rows):
for j in range(1, cols):
path_dp[i][j] = path_dp[i][j-1] + path_dp[i-1][j]
# Destination coordination = (rows-1, cols-1)
return path_dp[rows-1][cols-1]
複雜度分析
時間複雜度: O( m * n )
O( m * n )，板子上的每個格子點都拜訪一次，對應到雙層迴圈內部的計算。
空間複雜度: O( m * n )
O( m * n )，板子上總共有O(m * n)個格子點，也是DP table的大小。
Reference
