HOT100力扣(40) 动态规划-爬楼梯

这道题本质就是斐波那契数列，是动态规划的入门第一题。

核心思路（一句话讲透）：

要爬到第 n 阶台阶，最后一步只有两种可能：

1. 从第 n-1 阶爬 1 阶上来
2. 从第 n-2 阶爬 2 阶上来 所以爬到第 n 阶的总方法数 = 爬到 n-1 阶的方法数 + 爬到 n-2 阶的方法数

. 完整解题步骤

1. 定义状态：用f(x)表示爬到第 x 阶台阶的总方法数
2. 推导转移方程：f(x) = f(x-1) + f(x-2)
3. 确定边界条件：
   • f(0) = 1：站在第 0 阶（起点），只有 1 种方法（不用爬）
   • f(1) = 1：爬到第 1 阶，只有 1 种方法（爬 1 阶）
4. 空间优化（滚动数组）： 因为f(x)只和f(x-1)、f(x-2)有关，不需要保存整个数组，只用 3 个变量滚动更新即可，空间复杂度从 O (n) 降到 O (1)。

不管名字怎么变，永远遵守：

新值 = 前一个值 + 前前一个值

这里：

• r永远是最新算出来的结果（对应 f (i)）
• q是上一轮的结果（对应 f (i-1)）
• p是上上轮的结果（对应 f (i-2)）

class Solution { public: int climbStairs(int n) { //r表示最后的可能 r等于前n-1和n-2的可能数的和 /*p：代表 f(i-2)（上上个台阶的方法数） q：代表 f(i-1)（上一个台阶的方法数） r：代表 f(i)（当前台阶的方法数）*/ //r=1 表示在从0到1台阶的方法只有一个 int p = 0,q = 0,r = 1; for(int i = 1;i<=n;i++){//从台阶1开始走 p = q;// q = r;// r = p +q; } return r; } };