Recursion: Davis' Staircase Discussions | | HackerRank

Recursion: Davis' Staircase

  • + 28 comments

    My first solution was a simple recursion with DP. Then I gave it more thought and came up with the following result:

    Solving this problem is like solving the following recursion:

    A(n) = A(n - 1) + A(n - 2) + A(n - 3)
    A(1)=1; A(2)=2; A(3)=4.
    

    A(n) represents the number of ways he can climb a staircaise of height n.

    This recursion is extremely similar to fibonacci so I thought a trick like matrix exponentiation should be possible, and apparently it is. The following equivalence is true:

    |A(n+2)  A(n+1)  A(n) | |1 1 0| |A(n+3)  A(n+2)  A(n+1)|
    |A(n+1)   A(n)  A(n-1)|*|1 0 1|=|A(n+2)  A(n+1)   A(n) |
    | A(n)   A(n-1) A(n-2)| |1 0 0| |A(n+1)   A(n)   A(n-1)|
    

    which means:

    |A(5)  A(4)  A(3)| |1 1 0|^n |A(n+5)  A(n+4)  A(n+3)|
    |A(4)  A(3)  A(2)|*|1 0 1|  =|A(n+4)  A(n+3)  A(n+2)|
    |A(3)  A(2)  A(1)| |1 0 0|   |A(n+3)  A(n+2)  A(n+1)|
    

    This means we can find expressions for A(2n) and A(2n + 1) in terms of A(n) (and parameters close to n). So a logN solution is possible using this approach.

    Of course, none of this is required to solve this problem because the constraints are very limited. I just gave it more thought because science.