HOT100力扣(40) 动态规划-爬楼梯
这道题本质就是斐波那契数列，是动态规划的入门第一题。
核心思路（一句话讲透）：
要爬到第 n 阶台阶，最后一步只有两种可能：
- 从第 n-1 阶爬 1 阶上来
- 从第 n-2 阶爬 2 阶上来 所以爬到第 n 阶的总方法数 = 爬到 n-1 阶的方法数 + 爬到 n-2 阶的方法数
. 完整解题步骤
- 定义状态：用
f(x)表示爬到第 x 阶台阶的总方法数 - 推导转移方程：
f(x) = f(x-1) + f(x-2) - 确定边界条件：
f(0) = 1：站在第 0 阶（起点），只有 1 种方法（不用爬）f(1) = 1：爬到第 1 阶，只有 1 种方法（爬 1 阶）
- 空间优化（滚动数组）： 因为
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; } };