Basically it's a fibonacci.


  • 225
    L

    The problem seems to be a dynamic programming one. Hint: the tag also suggests that!
    Here are the steps to get the solution incrementally.

    • Base cases:
      if n <= 0, then the number of ways should be zero.
      if n == 1, then there is only way to climb the stair.
      if n == 2, then there are two ways to climb the stairs. One solution is one step by another; the other one is two steps at one time.

    • The key intuition to solve the problem is that given a number of stairs n, if we know the number ways to get to the points [n-1] and [n-2] respectively, denoted as n1 and n2 , then the total ways to get to the point [n] is n1 + n2. Because from the [n-1] point, we can take one single step to reach [n]. And from the [n-2] point, we could take two steps to get there. There is NO overlapping between these two solution sets, because we differ in the final step.

    Now given the above intuition, one can construct an array where each node stores the solution for each number n. Or if we look at it closer, it is clear that this is basically a fibonacci number, with the starting numbers as 1 and 2, instead of 1 and 1.

    The implementation in Java as follows:

    public int climbStairs(int n) {
        // base cases
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        int one_step_before = 2;
        int two_steps_before = 1;
        int all_ways = 0;
        
        for(int i=2; i<n; i++){
        	all_ways = one_step_before + two_steps_before;
        	two_steps_before = one_step_before;
            one_step_before = all_ways;
        }
        return all_ways;
    }

  • 1
    Z

    This is a fantastic solution, also great explanation.


  • 15

    I like the variable naming.


  • 2
    I

    I understood the Fibonacci pattern part but got confused by the variable names(one_step_before, two_step_before), their initial values and how their values are exchanged. Can someone explain please?


  • 21
    L

    To the question of @imaginatives, here are some more explanations on the code.

    So the "all_ways" corresponds to the number of solutions to get to the point [n].
    And "one_step_before" refers to the number of solutions until the point [n-1],
    "two_steps_before" refers to the number of solution until the point [n-2].

    From the point [n-1], we take one step to reach the point [n].
    From the point [n-2], we take a two-steps leap to reach the point [n].

    So it goes without saying that the total number of solution to reach the point [n] should be [n-1] + [n-2].


  • 0
    Q

    i think for n<=0, the job is already finished, so there is 1 way to finish the climing -- not climing, similar with factorial(0)==1.
    under this consideration, 2 base cases suffices, 1 for n<=0, 1 for n==1.

    int x=1,y=1;
    for(;n-->0;) {
    	y=y+x;
    	x=y-x;
    }
    return x;

  • 0
    L

    @qeatzy. The "n<=0" case is more of input sanitation, as well as a base case. The program would still be correct, if we remove the check if ( n<=0 ) return 0;

    I think it is nicer to do the check at the beginning of the function, instead of letting the rest of the function handle the less expected 'input'.


  • 3
    D

    thanks for a good solution and explanation!
    Looks like your one_step_before and two_steps_before were mixed up. It doesn't affect the correctness though. Just confusing. when n = 3, one_step_before should be 2. two_steps_before should be 1. right?


  • 2
    L

    Indeed. Thanks for pointing that out.


  • 0
    D

    I understood it was fibonacci just by writing down the sequence up to n = 5. What I don't get though is why there is no overlap between [n-2] and [n-1].


  • 0
    L

    There could have been some overlapping "steps" for the solution number at p[n-1] and p[n-2].

    But the final step tells these solutions apart, since from the point p[n-1], one take a one-step jump to reach the destination, while from the point p[n-2] one takes a two-steps leap.


  • 6
    G

    I would not not put this question in easy category, it can be demoralizing :)


  • 1
    G

    I think there is a small bug in the code.
    it should be
    int one_step_before = 1;
    int two_steps_before = 2;

    instead of
    int one_step_before = 2;
    int two_steps_before = 1;


  • 0
    L

    I agree with u.:P


  • 0
    H

    The result is wrong because of minor error in the code. Below is the corrected.

    all_ways = one_step_before + two_steps_before;
    		two_steps_before =  one_step_before ;
    		one_step_before = all_ways;

  • 3
    E

    Yes, it is indeed Fibonacci series. It is worthwhile to point out that the nth Fibonacci can be computed in log(n) time. See this link for the code and explanation: The Nth Fibonacci Number in O(log N)

    The bottom up (iterative) approach in this case is better than top down (recursive) approach, but I am posting my top down answer anyway for those who might be interested:

    public int climbStairs(int n) {
        int[] res = new int[n+1];
        return getValue(n, res)[n];
    }
    
    public int[] getValue(int n, int[] res) {
        if(n==0) 
            res[0] = 1;
        else if(n==1)
            res[1] = 1;
        else if(res[n] == 0)
            res[n] = getValue(n-1, res)[n-1] + getValue(n-2, res)[n-2];
            
        return res;
    }
    

  • 2

    That code isn't O(log N) but only O(N).


  • 0
    C

    agree with huijie2
    {
    two_steps_before = one_step_before ;
    one_step_before = all_ways;
    }
    is more reasonable. Although the result is the same.


  • 0
    C

    Nice answer!

    +1 huijie2

    it should be (also makes semantic sense)

    two_steps_before = one_step_before ;
    one_step_before = all_ways;


  • 7
    V

    3 line solution for anyone interested :)

    public int climbStairs(int n) {
        int answer = 1;
        for(int i = 0, pre = 0; i < n; i++) pre = (answer += pre) - pre;
        return answer;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.