I want to ask how do you figure this relation out. Can anyone explain it literally?


  • 8
    A

    Hi,
    After thinking your code, I found the relation between the ways like a Fibonacci number.

    But how do you guys figure this relation out?

    Does it have logical literally explanation?

    Hope anyone can help me.

    Thanks a lot.


  • 26
    C

    Hi,

    I didn't recognise that it was a Fibonacci number the first minute so I followed the lead of a recursive solution:

    Can I figure out the number of solutions for a N steps stair (which I'll name S[N]) if I already know the number of solutions for a N-1 steps stair?

    From any N-1 solution I can just climb another step to get a N steps solution.

    Therefore the answer S[N] is at least equal to S[N-1].

    Now we have forgotten all the solutions which end by a 2 steps climb. This set of solutions is equal to S[N-2] (because there is room for a 2 steps climb).

    We conclude that S[N] = S[N-1] + S[N-2].

    And suddenly you find yourself thinking about the reproduction rate of rabbits.

    Hope it helps


  • 0
    A

    Thank you very much!
    You explain it clearly!
    I suddenly understand the solution's meaning.
    It's helpful!


  • 0
    S

    Hi @Coddy, thanks for your answer! However, I have a question. If we say that S[N] = S[N-1]+S[N-2] doesnt it mean that we count S[N-2] twice, since it is contained in S[N-1]? I am not quite convinient that this is the recursive relationship?


  • 0
    C

    it is not count S[N-2] twice, it is that after you have climbed N-2 stair, then you climb 2 stair you will reach the N stair, S[N-1] is that after you have climbed N-1 stair, you only need to climb one stair so as to reach N stairs.


Log in to reply
 

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