目录一.题目描述二.解题思路三.代码四.重点一.题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶提示1 n 45二.解题思路①核心规律解题关键达到第3个台阶的方法数 达到第1个台阶的方法数因为是第1个台阶迈两步上来的 达到第2个台阶的方法数因为是第2个台阶迈一步上来的。抽象为表达式dp[ i ] dp[ i-2 ] dp[ i-1 ]我们此时没抽象成数组而是抽象成了一个变量都一样能状态转换让for循环跑起来就行int current prev2 prev1;//计算达到当前台阶的总数往前数两个的那个台阶的方法数 往前数一个的那个台阶的方法数②由于这道题规定了每次最多爬2个台阶因此我们要有一个分工意识。即当n2时用if判断单独返回步数因为简单很好判断起步当n2时需要用for循环来实现动态规划算法状态压缩状态转换来计算达到第n个台阶的最大方法数跑起来不断进行状态转换最终求出结果③由于这道题规定了每次最多爬2个台阶因此我们只需要定义2个初始变量prev2、prev1。同理如果以后这道题换一个出法比如每次最多可以爬3个台阶那么就需要定义3个初始变量prev3、prev2、prev1了这也很好理解因为后续需要进行状态转换。④关键思想用for循环实现动态规划算法的时候其实就是模拟从下慢慢往上爬的过程每爬一步以后prev2、prev1就需要更新最新的值。比如我现在在第三个台阶此时的前两个台阶是第一阶前一个台阶是第二阶。那么当我往上爬了一层以后现在到了第四层新的前两个台阶就变成了第二阶新的前一个台阶就变成了第三阶。这也不难理解纯属生活常识。上述状态转换的过程就可以写成如下的代码prev2 prev1;//很好理解当又往上爬了一个台阶新的往前数两个的台阶的最大方法数 旧的往前数一个的台阶的最大方法数prev1 current;//很好理解当又往上爬了一个台阶新的往前数1个的台阶的最大方法数 旧的当前台阶的最大方法数三.代码class Solution { public int climbStairs(int n) { //这个不难理解 //当n1,方法就1种1n //当n2,方法就2种2n if(n2){ return n; } int prev2 1;//当前台阶往前数两个的方法数初始化为第三阶往前数两个即第1阶方法数就1个 int prev1 2;//当前台阶往前数一个的方法数初始化为第三阶往前数一个即第2阶方法数有2个 for(int i3; in; i){ //计算达到当前台阶的总数往前数两个的那个台阶的方法数 往前数一个的那个台阶的方法数 //举例达到第三个台阶的方法数 达到第二个台阶的方法数2 达到第一个台阶的方法数1 3 int current prev2 prev1; //状态转换核心步骤 prev2 prev1;//很好理解当又往上爬了一个台阶新的往前数两个的台阶 旧的往前数一个的台阶 prev1 current;//很好理解当又往上爬了一个台阶新的往前数1个的台阶 旧的当前台阶 } //最后的prev1就是所求的值思考为什么不是current因为for循环结束时把current赋给了prev1 return prev1; } }运行效果四.重点①知道初始变量怎么定义本题是根据一次最多迈多少个台阶来决定的②知道解题的分工用if解决前2个台阶用for解决2~n个台阶③知道状态转换的逻辑prev2 prev1;//很好理解当又往上爬了一个台阶新的往前数两个的台阶 旧的往前数一个的台阶prev1 current;//很好理解当又往上爬了一个台阶新的往前数1个的台阶 旧的当前台阶本题只是一个简单的动态规划问题希望它成为一个引子启蒙大家对于动态规划算法的学习。