Climbing Stairs (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返回的结果.依次类推.

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

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