Dynamic Programming in Go #2: Climbing Stairs
The requirement is to find out number of paths that are available to climb given number of stairs provided you can climb at best 3 stairs at once.
Naive Method: Test
We talked about memoization here: https://hitesh-pattanayak.medium.com/dynamic-programming-in-go-1-fibonacci-68d2b7f1b616
Memoized Method: Test
There are 3 steps associated with this method:
- Storage and Meaning
- Travel and Solve
We know for a fact that, we have to climb ’n’ stairs.
So we create a ‘Storage’ that will store (‘Meaning’) count of all possible paths from that step. So basically the size of the ‘Storage’ would be ‘n+1’.
Now ‘Direction’ implies, from which direction will it be easier to solve.
For example, we can climb ‘1’ steps at the end because there are no further stairs, only thing we can climb at the last stair is itself.
Subsequently, we can climb ‘1’ steps at the penultimate too because there is only 1 stair left to climb, and we cannot take 2 or 3 steps but only 1.
Subsequently, we can climb ‘2’ steps at the last but 2 stair because either we can climb 1 stair to reach penultimate or climb 2 stairs to reach end.
So we can infer that, TotalPaths(n) = TotalPaths(n+1) + TotalPaths(n+2) + TotalPaths(n+3).
So the ‘Direction’ is backwards.
Tabulation Method: Test
How can we measure the difference in performance of the methods?
If we run the ‘Naive Method’ to find number of paths to climb 10 stairs, it takes ‘1279’ nano seconds.
But if we run the ‘Memoized Method’ to find number of paths to climb 10 stairs, it takes ‘86.13’ nano seconds.
But again if we run the ‘Tabulation Method’ to find number of paths to climb 10 stairs, it takes ‘41.44’ nano seconds.
Folks, if you like my content, would you consider following me on linked in at: https://www.linkedin.com/in/hitesh-pattanayak-52290b160/