class Solution { public: int climbStairs(int n) { if(n 2) return n; vectorint dp(n 1); // dp[i]到達(dá)第 i 個臺階有幾種方法 dp[1] 1; dp[2] 2; for(int i 3; i n; i){ // 最后一步走1階或2階 dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };總結(jié)這道題最重要的是理解dp[i]表示到達(dá)第i個臺階一共有多少種方法。到達(dá)第i階最后一步只有兩種可能① 從第i-1階走 1 步dp[i-1]② 從第i-2階走 2 步dp[i-2]所以dp[i] dp[i-1] dp[i-2];為什么dp[1] 1dp[2] 2第1階 1只有一種。第2階 1 1 2有兩種。所以dp[1] 1; dp[2] 2;然后不斷往后推dp[1] 1 dp[2] 2 dp[3] 3 dp[4] 5 dp[5] 8 ...你這次解決的兩個易錯點①vector大小vectorint dp(n 1);因為需要訪問dp[n]所以必須開n 1個位置。②n 2的邊界if(n 2) return n;避免n 1時還去訪問dp[2]導(dǎo)致越界。最后記住這個 DP 模板1. 定義 dp[i]第 i 個狀態(tài)代表什么 2. 找最后一步/最后一個狀態(tài)怎么來的 3. 寫狀態(tài)轉(zhuǎn)移方程 4. 初始化最前面的狀態(tài) 5. 從前往后推 6. 返回 dp[n]這道題就是最基礎(chǔ)的線性 DP核心公式dp[i] dp[i - 1] dp[i - 2];本質(zhì)上就是斐波那契數(shù)列。