Now that we have already discussed the basics of dynamic programming let us discuss another DP problem.

Staircase problem is another classic DP question which can be solved using 1D array, similar to Fibonacci number problem we already discussed.

Pseudocode discussed here can easily be translated to Python.

Problem statement:

Given a staircase with 'n' stairs, calculate how many ways are there to reach the top if one can take either 1, 2 or 3 steps at a time. eg.

if n=2, no of ways to reach top = 2 {1,1}, {2}

if n=3, no of ways to reach top = 4 {1,1,1}, {1,2}, {2,1}, {3}

if n=4, no of ways to reach top = 7 {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, {2,2}, {1,3}, {3,1}

Let us now see how this problem can be broken down to Dynamic Programming structure.

Overlapping sub-problem structure:

Since a person can take 1, 2 or 3 steps at a time, this is how our approach will look like:

total = ways(n-1) + ways(n-2) + ways(n-3)

We will now see 3 approach to solve this:

1. Recursive
2. memoization
3. tabulation

1. Basic Solution by recursion

def ways(n):
    # base case
    if n == 0  return 1  
    if n == 1  return 1
    if n == 2  return 2

    return ways(n-1) + ways(n-2) + ways(n-2)

ways(5)

2. Top down DP with Memoization

dp = array of size n+1
def ways(n):

# base case
if n == 0  return 1  
if n == 1  return 1
if n == 2  return 2

if dp[n] == 0 then:
    dp[n] = ways(n-1) + ways(n-2) + ways(n-2)
return dp[n]

As we can see above, everytime we solve a sub-problem we store the solution in an array for future reference. This saves us from recalculating the same sub-problem repeatedly which we do in the basic recursive solution.

3. Bottom up DP with Tabulation

def ways(n):
  dp = array of size (n+1)
  dp[0] = 1
  dp[1] = 1
  dp[2] = 2

  for i in range(3, n+1):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

  return dp[n]

In this approach, we avoid recursion and calculate for every possible sub-problem.

Time and space complexity:

Recursive approach: time: O(3^n) space: O(n)

Memoization: time: O(n) space: O(n)

Tabulation: time: O(n) space: O(n)

Now that we have the pseudocode for all approaches, try to solve this problem on LeetCode

Do attempt to solve these on your own before looking at the solutions here

Share your code in comments.

You can also comment for any clarifications/feedback.

Follow me for more content to crack your coding interviews. I will be covering all 5 patterns of Dynamic programming questions in Aug so stay tuned !

Happy coding. Cheers !