力扣刷题之爬楼梯（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<Integer,Integer> map = new HashMap<Integer,Integer>();
    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<Integer,Integer> map = new HashMap<Integer,Integer>();
//         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返回的结果。依次类推。

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

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