LeetCode：70. 爬楼梯

简介

题目链接：https://leetcode.cn/problems/climbing-stairs/description/

解决方式：递归、递归 + 记忆化（记忆化搜索）、动态规划

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

推荐查看灵茶山艾府大佬所作题解。

递归

解题思路：从最后一步往前看，最后一步只有两种方式，一种是一步，一种是两步。如此循环将大的问题拆解成了性质相似的小问题进行求解。

// 会超时的递归代码classSolution{publicintclimbStairs(intn){returndfs(n);}privateintdfs(inti){// 递归终止条件if(i<=1){return1;}// 递归公式returndfs(i-1)+dfs(i-2);}}

由于递归过程中会产生大量的重复计算，所以该方法会超出时间限制。

递归 + 记忆化

这种方法也叫做记忆化搜索。

解题思路：既然递归会产生大量的重复计算，那就通过数组的手段，存储计算过的值，此后再遇到相同值的计算就直接返回存储的值即可。

classSolution{publicintclimbStairs(intn){// 递归 + 记忆化// 记住递归过程中算过的值，避免后续重复计算，导致时间超出int[]memos=newint[n+1];returndfs(n,memos);}// 递归函数privateintdfs(inti,int[]memos){// 递归终止条件if(i<=1){return1;}// 值之前已经算过，返回算过的值的方法if(memos[i]!=0){returnmemos[i];}// 递归公式// 记忆当前值的台阶的不同方法，防止重复计算returnmemos[i]=dfs(i-1,memos)+dfs(i-2,memos);}}

动态规划

解题思路：动态规划解题有三个部分：状态定义、状态转移方程式、初始值与边界。至于如何进行状态的定义，需要每一位读者去感悟、发现，因为题目的要求是不一样的，没有固定的模版。

非空间最优

classSolution{publicintclimbStairs(intn){int[]dp=newint[n+1];// 状态的定义。爬到台阶 n 处所有的方法。// 初始值 + 边界dp[0]=dp[1]=1;// 状态转移方程式// 从下往上算（递推）for(inti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}// 返回结果returndp[n];}}

空间优化

值得注意的是，空间优化后的可读性十分不好。

classSolution{publicintclimbStairs(intn){// 空间优化// 由状态转移方程式 dp[i] = dp[i - 1] + dp[i - 2] 可知// 下一个值的计算只需要知道上一个计算结果和上上一个计算结果intf0=1;intf1=1;for(inti=2;i<=n;i++){intnewf=f0+f1;// 对于下一个值的计算，newf 相当于上一个计算结果，f1 就是上上一个计算结果f0=f1;f1=newf;}// 返回数据returnf1;}}