0 ms Easy understanding C solution


  • 2
    D

    To get to the last stair n, let's assume we have s(n) kinds of methods, then s(n) = s(n-1) + s(n-2), and for the first stair, we have s(1) = 1 kind of way, for second stair, we have s(2) = 2 kinds of different ways since we can first go to stair #1 and then stair #2 or directly stair #2 from the start.

    Then it comes to our code:

    int climbStairs(int n) {
        int exex, ex, ans;
        if(n<=2) return n;
        
        exex = 1, ex = 2; // prepare for the start condition
        for(int i=3; i<=n; i++)
        {
            ans = exex + ex;
            exex = ex; // one step forward
            ex = ans; // one step forward
        }
        return ans;
    }

  • 0
    D

    why s(n) = s(n-1)+s(n-2)?


  • 0
    D

    let's assume you have s(n-1) ways to get to node#n-1, and you have s(n-2) ways to get to node#n-2, no matter how many ways you can choose to get to node#n-1, you have exactly only one way to node#n from node#n-1. the same to node#n-2, no matter how many ways you have to get to node#n-2, for each way, you have only one choice to get node#n from node#n-2.


  • 0
    D

    Thus the sum of choices to get to node#n is the sum of s(n-1)+s(n-2)


  • 0
    D

    this problem can be solved iteratively and recursively, and you can try them both.


  • 0
    D

    recursive solution is easy to write, however, you will fail to pass the test cases since every call and return cost far more time than iterative solution. Here is one possible recursive solution:

    int climbStairs(int n) {
    if(n<=2) return n;
    else return climbStairs(n-1) + climbStairs(n-2);
    }


  • 0
    F

    I don't know why,I saw you named ex..exex...,I couldn't help laughing....Ex-girlfriend EX-Ex-girlfriend!!


  • 0
    D

    well, then you seem to have a lot of stories other than programming ~


  • 0
    N

    I think this logic is flawed for n>5 stairs. When it's worked out on paper, I get:
    n[5] = 8
    n[6] = 12
    n[7] = 18

    this clearly does not hold the pattern above.

    For instance, for n[7], there is 1 way to take one step at a time, 6 ways to take one double step, 7 ways to take two double steps, and 4 ways to take three double steps:

    1+6+7+4 = 18 . . .


  • 0
    D

    could you tell me how you got n[7] because I think n[7] = 21:
    zero 2-step: 1;
    one 2-step: 6;
    two 2-step: 10, (A(5,5) / (A(2,2)A(3,3)));
    three 2-step: 4;
    and the sum is 21 instead of 18, please do tell me if i was wrong.


  • 0
    N

    The way that I did it, the elements of n[7] are:

    n[7] = { 1111111,

    211111, 121111, 112111, 111211, 111121, 111112,

    22111, 21211, 21121, 21112, 12112, 11212, 11122,

    2221, 2212, 2122, 1222 }

    or count(n[7]) = 18

    It makes more sense to draw it out on paper.

    Did I miss elements?


  • 0
    N

    Never mind. My sort logic on the "two 2-step" events skipped some of the mid-conditions
    {11221, 12121, 12211}


  • 0
    D

    that's it. You get it!


Log in to reply
 

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