Why Fibonacci sequence is the solution of this problem ?


  • 0
    A

    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
    K

    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
    S

    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
    A

    @subfallen Ok get it Thank you very much


  • 0
    G

    @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.