DP動態規劃 深入淺出 以Number of Ways to Stay in the Same 為例
這題算是路徑計數類的DP衍伸題(路徑數、方法數、組合數...等等這種枚舉類的題目，第一時間切入除了想到DFS+回溯法之外，也可以留意DP動態規劃解題的可能性)
題目敘述
題目會給我們一個指定長度為arrLen的陣列，起點從index=0開始出發，每次移動可以往左移一格，往右移一格，或是留在原地不動。問我們在steps步之後，恰好停在index=0的方法數有幾種?
最後輸出時，題目要求對109 + 7取餘數作為答案。
詳細的題目可在這裡看到
測試範例
Example 1:
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
Example 2:
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
Example 3:
Input: steps = 4, arrLen = 2
Output: 8
Dynamic programming的解題框架
再次複習Dynamic programming的解題框架，可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
1. 定義狀態 [我在哪裡]
我們可以定義DP(step, position) = 總共耗費step步，目前停在position這個格子的方法數
那麼最終DP(steps, position=0) 就是我們的解答，也是最後輸出結果。
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
每一步只有三種選擇，要麼往左一格，要麼往右一格，要麼留在原地。
DP(step, position)
= 前一步從左邊走過來 + 前一步從右邊走過來 + 前一步剛好同一個格子
= DP(step-1步，左邊那格)+DP(step-1步，右邊那格)+DP(step-1步，留在原地)
= DP(step-1, position-1) + DP(step-1, position+1) + DP(step-1, position)
3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]
第一步題目已經說從index=0出發，所以
DP(step=0, position=0) = 1 唯一一種方法
另外，當step扣到比零還小時，代表用盡所有步數，不能再走了，所以
DP(step< 0, position) = 0
還有，當position超出邊界時，代表非法情況，不能再走了，所以
DP(step0, position < 0 或者 position >= arrLen ) = 0
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
程式碼
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
dp = {}
CONSTANT = 10**9+7
def count(step, position):
if( step, position) in dp:
# Look-up DP table
return dp[ step, position]
if step < 0 or not( 0 <= position < arrLen ):
# Run out of steps, or out of valid array position
return 0
if step == 0 and position == 0:
# Reach base case
return 1
# Three way to reach current position:
# One step left, Keep staying, on step right
cur = (count(step-1, position-1) + count(step-1, position) + count(step-1, position+1)) % CONSTANT
dp[step, position] = cur
return cur
#=====================================
return count(step=steps, position=0)
複雜度分析
時間複雜度:
O( m * n )
二維DP，一個維度是steps，另一個維度是position。
空間複雜度:
O( m * n )
二維DP，一個維度是steps，另一個維度是position。
需要維護一個二維的DP table。
此外，遞迴呼叫的recursion call stack最深深度也是二維，O(m * n )
Reference:
