leetcode 70爬楼梯

class Solution { public: int climbStairs(int n) { if(n 2) return n; vectorint dp(n 1); // dp[i]到达第 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]; } };总结这道题最重要的是理解dp[i]表示到达第i个台阶一共有多少种方法。到达第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]导致越界。最后记住这个 DP 模板1. 定义 dp[i]第 i 个状态代表什么 2. 找最后一步/最后一个状态怎么来的 3. 写状态转移方程 4. 初始化最前面的状态 5. 从前往后推 6. 返回 dp[n]这道题就是最基础的线性 DP核心公式dp[i] dp[i - 1] dp[i - 2];本质上就是斐波那契数列。