企业官网建设流程全解析

class Solution { public: int climbStairs(int n) { if(n <= 2) return n; vector<int> 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] = 1，dp[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大小

vector<int> 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];

本质上就是斐波那契数列。