这道题本质就是斐波那契数列是动态规划的入门第一题。核心思路一句话讲透要爬到第 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)当前台阶的方法数*/ //r1 表示在从0到1台阶的方法只有一个 int p 0,q 0,r 1; for(int i 1;in;i){//从台阶1开始走 p q;// q r;// r p q; } return r; } };