Dynamic Programming in Go #2: Climbing Stairs

Hitesh Pattanayak
3 min readJun 14, 2022

--

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

Naive Method: Test

Memoized Method

We talked about memoization here: https://hitesh-pattanayak.medium.com/dynamic-programming-in-go-1-fibonacci-68d2b7f1b616

Memoized Method: Test

Tabulation Method

There are 3 steps associated with this method:

  1. Storage and Meaning
  2. Direction
  3. 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?

By Benchmarking

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/

--

--

Hitesh Pattanayak

Senior Product Engineer @ Infracloud Technologies | 7 years of experience | Polyglot | Backend Developer | Kubernetes and AWS practitioner | Finance Enthusiast