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.
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
Thank you very much!
You explain it clearly!
I suddenly understand the solution's meaning.
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?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.