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

  • 8

    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


    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

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

  • 0

    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

    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.