DP動態規劃 深入淺出 以Unique Path 路徑總數 為例_精選75題

如同這個Dynamic programming 深入淺出系列的開始，在經過比較簡單的入門題(Coin Change)之後，來看比較進階的二維DP題目Unique Path

學而時習之不亦樂乎，再次強調DP的解題框架，鞏固知識點。

Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。

Dynamic programming的解題框架可分為三大步驟

1.定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

題目敘述

詳細的題目可在這裡看到 Unique Paths

題目給定我們一個棋盤的高與寬，起點固定在左上角，終點固定在右下角。

每一步只能選擇往右走一格，或者往下走一格，不能回頭。

要求我們求出從起點到終點有幾條路徑。

對應的解題影片，搭配服用，效果更佳。

測試範例

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

[1] Python/JS/Java/Go/C++by O( mn ) DP [ With explanation ]