力扣刷题之爬楼梯（7/30）

力扣刷题之爬楼梯（7/30）

力扣刷题之爬楼梯

题目如下

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这道题的要求的话是很清晰的，也就是我们一步楼梯可以有两种走法，就是一次一层还有就是一次两层。上一层的当然只有一种，然后上两层的话有两种，就是一步一步，或者一次性走两层。上三层的话的方法就是走一层和走两层的方法的和。这个只体现的方法的数量上。

第n个层可以从n-1一步到达，也可以从n-2采用两种方法到达。 所以呢!可以列出一个方法的函数表达式 f（n）= f(n-1)+f(n-2)。这样就确定了一个递推的公式,我们可以递归去计算，但是要考虑递归的出口，当n等于2的时候需要去直接给定一个值为2，因为计算f(0)是不合理的，所以我们这样去考虑了。

我们可以首先这样去做，是这样的一个逻辑

package leetcode;/** * @author 兰舟千帆 * @version 1.0 * @date 2022/7/30 9:37 */public class CommonFactor { public static void main(String[] args) { int n = 10; function_count(n); } public static int function_count(int n) { if (n==1||n==2) { return n; } return function_count(n-1)+function_count(n-2); }}

但是放在力扣的话，运行的话。

这样的话，力扣这里测试的话，就狐疑超出时间的限制。因为递归是比较消耗时间的。

其实可以思考一下，我们的递归简单的有没有去优化的方法，可以这样去思考一个问题，比如我们计算从第一层到第五层的方法数，我们需要在递归里面用f（4）+f(3)，然后这两层就一直递归到借宿条件，所以这里存在重复的计算

f(4)=f(3)+f(2)f(3)=f(2)+f(1)

对于这里我们可以这样去想，如果f(4)中通已经递归计算出f(3)，那么我们就就没有必要再去计算f(3)了，我们直接去用已经计算出的这个结果不就行了？为什么还有去算呢？我们这样去优化，众所周知，HashMap不允许重复的键。

于是呢，我们可以这样去写

class Solution { Map map = new HashMap(); public int climbStairs(int n) { if(n==1||n==2) { return n; } else if(null!=map.get(n)){ return map.get(n); }else{ int result = climbStairs(n-1)+climbStairs(n-2); map.put(n,result); return result; } }}

这样优化的递归毫不逊色。

上面这两种方法的话，本质上还是递归。递归的话，你可以去想象为一颗树，我们从树的根乡下对孩子和叶子进行遍历处理，最后再返回结果。这是一种至顶向下的方法。

我们可以采用至底向上累加的方法

class Solution { public int climbStairs(int n) {// Map map = new HashMap();// if(n==1||n==2)// {// return n;// }// else if(null!=map.get(n)){// return map.get(n);// }else{// int result = climbStairs(n-1)+climbStairs(n-2);// map.put(n,result);// return result;// } int result =0; int n1 =2; int n2 =1; if (n==1||n==2) { return n; } for(int i=3;i<=n;i++) { result = n1+n2; n2 = n1; n1 = result; } return result; }}

其实它很类似于反向的递归，但是这种方法比递归还好理解，非常的巧妙。 其实就类似于这样的树。最底部的就是1,2，然后依次累计上去，同时for循环里面存在一个复制和交换，这样就可以认为在B已经累加出来后，同时又指定了c,但是c的值我们已经计算出来了，就是上一个result返回的结果。依次类推。

但是力扣的解题大神总是出乎意料的牛逼，不过在牛逼的基础上其实还是懂得更多。

然后他就一直计算下去了，我打赌，他之前的方法一定是超时了，所以才这样去超出三界的方式去解题了。秀。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。