CJ

Explore

Tracks

My Courses

Edpresso

Refer a Friend

Create

Grokking Dynamic Programming Patterns for Coding Interviews

97% completed

Introduction

What is Dynamic Programming?

Pattern 1: 0/1 Knapsack

0/1 Knapsack

Equal Subset Sum Partition

Subset Sum

Minimum Subset Sum Difference

Count of Subset Sum

Target Sum

Pattern 2: Unbounded Knapsack

Unbounded Knapsack

Rod Cutting

Coin Change

Minimum Coin Change

Maximum Ribbon Cut

Pattern 3: Fibonacci Numbers

Fibonacci numbers

Staircase

Number factors

Minimum jumps to reach the end

Minimum jumps with fee

House thief

Pattern 4: Palindromic Subsequence

Longest Palindromic Subsequence

Longest Palindromic Substring

Count of Palindromic Substrings

Minimum Deletions in a String to make it a Palindrome

Palindromic Partitioning

Pattern 5: Longest Common Substring

Longest Common Substring

Longest Common Subsequence

Minimum Deletions & Insertions to Transform a String into another

Longest Increasing Subsequence

Maximum Sum Increasing Subsequence

Shortest Common Super-sequence

Minimum Deletions to Make a Sequence Sorted

Longest Repeating Subsequence

Subsequence Pattern Matching

Longest Bitonic Subsequence

Longest Alternating Subsequence

Edit Distance

Strings Interleaving

Appendix

Contact Us

Other courses

Mark Course as Completed

Staircase

We'll cover the following

Problem Statement

Basic Solution

Top-down Dynamic Programming with Memoization

Bottom-up Dynamic Programming

Code

Memory optimization

Fibonacci number pattern

Problem Statement #

Given a stair with ‘n’ steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3
Number of ways = 4
Explanation: Following are the four ways we can climb : {1,1,1}, {1,2}, {2,1}, {3}

Example 2:

Number of stairs (n) : 4
Number of ways = 7
Explanation: Following are the seven ways we can climb : {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1},
{2,2}, {1,3}, {3,1}

Let’s first start with a recursive brute-force solution.

Basic Solution #

At every step, we have three options: either jump 1 step, 2 steps, or 3 steps. So our algorithm will look like this:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class Staircase {

public int CountWays(int n) {
if( n == 0)
return 1; // base case, we don't need to take any step, so there is only one way

if(n == 1)
return 1; // we can take one step to reach the end, and that is the only way

if(n == 2)
return 2; // we can take one step twice or jump two steps to reach at the top

// if we take 1 step, we are left with 'n-1' steps;
int take1Step = CountWays(n-1);
// similarly, if we took 2 steps, we are left with 'n-2' steps;
int take2Step = CountWays(n-2);
// if we took 3 steps, we are left with 'n-3' steps;
int take3Step = CountWays(n-3);

return take1Step + take2Step + take3Step;
}

public static void main(String[] args) {
Staircase sc = new Staircase();
System.out.println(sc.CountWays(3));
System.out.println(sc.CountWays(4));
System.out.println(sc.CountWays(5));
}
}

RUN

SAVERESET

The time complexity of the above algorithm is exponential O(3n)O(3^n)O(3​n​​) as we are making three recursive call in the same function. The space complexity is O(n)O(n)O(n) which is used to store the recursion stack.

Let’s visually draw the recursion for CountWays(4) to see the overlapping subproblems:

Recursion tree for calculating Fibonacci numbers

We can clearly see the overlapping subproblem pattern: CountWays(2) and CountWays(1) have been called twice. We can optimize this using memoization.

Top-down Dynamic Programming with Memoization #

We can use an array to store the already solved subproblems. Here is the code:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class Staircase {

public int CountWays(int n) {
int dp[] = new int[n+1];
return CountWaysRecursive(dp, n);
}

public int CountWaysRecursive(int[] dp, int n) {
if( n == 0)
return 1; // base case, we don't need to take any step, so there is only one way

if(n == 1)
return 1; // we can take one step to reach the end, and that is the only way

if(n == 2)
return 2; // we can take one step twice or jump two steps to reach at the top

if(dp[n] == 0) {
// if we take 1 step, we are left with 'n-1' steps;
int take1Step = CountWaysRecursive(dp, n-1);
// similarly, if we took 2 steps, we are left with 'n-2' steps;
int take2Step = CountWaysRecursive(dp, n-2);
// if we took 3 steps, we are left with 'n-3' steps;
int take3Step = CountWaysRecursive(dp, n-3);
dp[n] = take1Step + take2Step + take3Step;
}

return dp[n];
}

public static void main(String[] args) {
Staircase sc = new Staircase();
System.out.println(sc.CountWays(3));
System.out.println(sc.CountWays(4));
System.out.println(sc.CountWays(5));
}
}

RUN

SAVERESET

What is the time and space complexity of the above solution? Since our memoization array dp[n+1] stores the results for all the subproblems, we can conclude that we will not have more than n+1n+1n+1 subproblems (where ‘n’ represents the total number of steps). This means that our time complexity will be O(N)O(N)O(N). The space complexity will also be O(n)O(n)O(n); this space will be used to store the recursion-stack.

Bottom-up Dynamic Programming #

Let’s try to populate our dp[] array from the above solution, working in a bottom-up fashion. As we saw in the above code, every CountWaysRecursive(n) is the sum of the previous three counts. We can use this fact to populate our array.

Code #

Here is the code for our bottom-up dynamic programming approach:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class Staircase {

public int CountWays(int n) {
int dp[] = new int[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;

for(int i=3; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

return dp[n];
}

public static void main(String[] args) {
Staircase sc = new Staircase();
System.out.println(sc.CountWays(3));
System.out.println(sc.CountWays(4));
System.out.println(sc.CountWays(5));
}
}

RUN

SAVERESET

The above solution has time and space complexity of O(n)O(n)O(n).

Memory optimization #

We can optimize the space used in our previous solution. We don’t need to store all the counts up to ‘n’, as we only need three previous numbers to calculate the next count. We can use this fact to further improve our solution:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class Staircase {

public int CountWays(int n) {
if (n < 2) return 1;
if (n == 2) return 2;
int n1=1, n2=1, n3=2, temp;
for(int i=3; i<=n; i++) {
temp = n1 + n2 + n3;
n1 = n2;
n2 = n3;
n3 = temp;
}
return n3;
}

public static void main(String[] args) {
Staircase sc = new Staircase();
System.out.println(sc.CountWays(3));
System.out.println(sc.CountWays(4));
System.out.println(sc.CountWays(5));
}
}

RUN

SAVERESET

The above solution has a time complexity of O(n)O(n)O(n) and a constant space complexity O(1)O(1)O(1).

Fibonacci number pattern #

We can clearly see that this problem follows the Fibonacci number pattern. The only difference is that in Fibonacci numbers every number is a sum of the two preceding numbers, whereas in this problem every count is a sum of three preceding counts. Here is the recursive formula for this problem:

CountWays(n) = CountWays(n-1) + CountWays(n-2) + CountWays(n-3), for n >=3

This problem can be extended further. Instead of taking 1, 2, or 3 steps at any time, what if we can take up to ‘k’ steps at any time? In that case, our recursive formula will look like:

CountWays(n) = CountWays(n-1) + CountWays(n-2) + CountWays(n-3) + ... + CountWays(n-k), for n >= k

Completed

←    Back
Fibonacci numbers

Next    →
Number factors

Report an Issue

Ask a Question