leetCode clock in-70 climbing stairs

leetCode clock in-70 climbing stairs

##topic

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

// 
var climbStairs = function(n) {
    if (n <= 2) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
};

// 
var climbStairs = function(n) {
    if (n <= 2) return n;

    var lastLast = 1;
    var last = 2;
    var now = lastLast + last;

    var time = n - 2;
    while (time--) {
        now = lastLast + last;
        lastLast = last;
        last = now;
    }

    return now;
};
 

This problem is a dynamic programming problem. You can think about it in the following ways: 1. When I am on the xth ladder, I have two choices: once I go up the 1st ladder and once I go up the 2nd ladder. Thinking in reverse, when I When I climbed to the nth ladder, I had two choices in the last step: one time to go up the 1st step ladder and one time to go up the 2nd step ladder, that is, F(n) = F(n-1) + F(n-2) , So we can easily solve it in a recursive way; 2. We can already convert a problem into the sum of two sub-problems. Now we only need to know the solution of the bottom problem to solve the problem. Obviously n = When 1, the result is 1, and when n = 2, the result is 2;

We can continuously find the third result based on the results of the first two, without using recursion, simply save the results of the first two calculations to get the final result through a loop.