Why Fibonacci sequence is the solution of this problem ?

  • 0

    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?

  • 0

    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.

  • 0

  • 2

    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. :)

  • 0

    @subfallen Ok get it Thank you very much

  • 0

    @subfallen This helps a lot! thank you!

Log in to reply

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