---

動態規劃解三步問題：LeetCode 面試題 08.01. 三步問題

---

1. 題目鏈接

LeetCode 面試題 08.01. 三步問題
題目要求：小孩上樓梯，每次可以走1、2或3步，計算到達第 n 階臺階的不同方式數，結果需對 1e9 + 7 取模。

---

2. 題目描述

• 輸入：整數 n，表示臺階數。
• 輸出：不同的方式數（模 1e9 + 7）。
• 約束條件：
  • 1 ≤ n ≤ 1e6
  • 結果可能超過 2^31 - 1，需取模處理。

---

3. 示例分析

示例 1：
輸入：n = 3
輸出：4
解釋：方式為 1+1+1, 1+2, 2+1, 3。

示例 2：
輸入：n = 4
輸出：7
解釋：新增方式如 1+3, 2+2, 3+1, 1+1+2 等。

---

4. 算法思路

動態規劃遞推

1. 狀態定義：
   • dp[i] 表示到達第 i 階的方式數。
2. 遞推公式：
   • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
   • 每次可從前3個臺階走1、2或3步到達當前臺階。
3. 初始條件：
   • dp[1] = 1, dp[2] = 2, dp[3] = 4。

空間優化

• 直接使用數組存儲所有狀態，空間復雜度為 O(n)。
• 可優化為滾動變量（見注意事項）。

---

5. 邊界條件與注意事項

1. 邊界處理：
   • n < 4 時直接返回初始值。
2. 取模運算：
   • 每次更新狀態后需立即取模，防止溢出。

---

6. 代碼實現與解析

class Solution {
public:const int MOD = 1e9 + 7;int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <= n; i++) {// 使用 long 避免中間結果溢出dp[i] = ( (long)dp[i-1] + dp[i-2] + dp[i-3] ) % MOD;}return dp[n];}
};

代碼解析

1. 初始化處理：
   • 直接處理 n ≤ 3 的邊界情況，返回初始值。
2. 動態規劃數組：
   • dp[i] 存儲到達第 i 階的方式數，初始化前3項。
3. 遞推計算：
   • 循環從 i = 4 開始，遞推公式使用 long 類型防止溢出。
   • 每次計算后立即取模，確保結果合法。
4. 返回值：
   • dp[n] 即為最終結果。

---

優化

1. 滾動變量優化：
   • 僅保留前3個狀態，空間復雜度降至 O(1)。

   int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;int a = 1, b = 2, c = 4, d;for (int i = 4; i <= n; i++) {d = ( (long)a + b + c ) % MOD;a = b;b = c;c = d;}return c;
   }
   

2. 統一取模邏輯：
   • 所有中間操作統一用 long 類型，避免隱式溢出。

---

總結

通過動態規劃遞推解決三步問題，關鍵點在于狀態轉移和取模處理。代碼使用 long 類型確保大數計算正確性，適用于 n ≤ 1e6 的場景。此方法可推廣至類似遞推問題（如泰波那契數），需注意數值溢出和空間優化。