Force buckled brush the stairs (7/30)

题目如下

假设你正在爬楼梯.需要 n 阶你才能到达楼顶.

每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢？

The requirements of this question are very clear,That is, we can have two ways to take one step of the stairs,One layer at a time and two layers at a time.Of course there is only one on the upper level,Then there are two types of upper floors,Just step by step,Or go two floors at a time.The way to go to three floors is the sum of the way to go one floor and two floors.This only reflects the number of methods.

第nlayers can ben-1一步到达,也可以从n-2There are two ways to get there.
所以呢!A function expression that can list a method
f（n）= f(n-1)+f(n-2).This establishes a recursive formula,We can do it recursively,But consider recursive exits,当n等于2When you need to directly give a value2,因为计算f(0)是不合理的,So we thought about it this way.

We can do this first,是这样的一个逻辑

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);
    }





}

But in the case of force buckle,运行的话.


这样的话,Click here to test the words,Doubt beyond the time limit.Because recursion is time-consuming.

其实可以思考一下,There is no way to optimize our recursion simply,You can think about a problem like this,For example, we count the number of methods from the first layer to the fifth layer,We need to use it in recursionf（4）+f(3),Then these two layers recurs all the way to the accommodation condition,So there is a duplication of calculations here

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

Here we can think of it this way,如果f(4)Zhongtong has been calculated recursivelyf(3),Then we don't need to calculate any moref(3)了,We can directly use the result that has been calculated？Why even bother？We optimize this way,众所周知,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;

        }
      
            
       
    }
}

Such optimized recursion is not inferior.

the above two methods,It's still recursive in nature.递归的话,You can think of it as a tree,We traverse the children and leaves from the root of the tree,最后再返回结果.This is a top-down approach.

We can use a bottom-up approach

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;
      
            
       
    }
}

In fact, it is very similar to reverse recursion,But this method is easier to understand than recursion,非常的巧妙.
In fact, it is similar to such a tree.The bottom one is1,2,Then add up sequentially,同时forThere is a copy and swap inside the loop,It can be assumed that there isBAfter it has been accumulated,Also specifiedc,但是cThe value of , we have already calculated,就是上一个result返回的结果.依次类推.

But Likou's problem-solving god is always unexpectedly awesome,However, on the basis of Niubi, I actually know more.

And then he kept calculating,我打赌,His previous method must have timed out,That's why this is the way to go beyond the Three Realms to solve problems.秀.