A lot of programmers have used Fibonacci sequence to solve this problem, i have tested the solutions and they work very well, howver i am interested to know "why Fibonaci is the solution" what is the theory behind?
I don't have any insight on to how to arrive at the Fibonacci sequence by just looking at the problem statement. However, I only figured out it was the Fibonacci sequence because I wrote all the combinations out for n = 1, 2, 3, 4, 5. I basically used pattern matching to arrive at the solution.
Imagine we are standing on step N.
Now, either we just took one step up (from N-1); or we took two steps up (from N-2). Those are the only possibilities! Every distinct path to step N corresponds to either a distinct path that ended at N-1; or a distinct path that ended at N-2.
So we have:
PathsToStep(N) = PathsToStep(N-1) + PathsToStep(N-2)
Where the degenerate cases are
PathsToStep(0) = 1
because there is only one way to climb zero stairs, and
PathsToStep(1) = 1
because there is only one way to climb one stair. :)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.