We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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:
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.
Recursion: Davis' Staircase
You are viewing a single comment's thread. Return to all 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) 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:
which means:
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.