We use cookies to provide you with an optimal experience and relevant communication.Learn more
Grokking Dynamic Programming Patterns for Coding Interviews
Ask Author
Back to course home

0% completed

Introduction
What is Dynamic Programming?
Introduction
0/1 Knapsack
Solution: 0/1 Knapsack
Equal Subset Sum Partition
Solution: Equal Subset Sum Partition
Subset Sum
Solution: Subset Sum
Minimum Subset Sum Difference
Solution: Minimum Subset Sum Difference
Count of Subset Sum
Solution: Count of Subset Sum
Target Sum
Solution: Target Sum
Unbounded Knapsack
Solution: Unbounded Knapsack
Rod Cutting
Solution: Rod Cutting
Coin Change
Solution: Coin Change
Minimum Coin Change
Solution: Minimum Coin Change
Maximum Ribbon Cut
Solution: Maximum Ribbon Cut
Fibonacci numbers
Solution: Fibonacci numbers
Staircase
Solution: Staircase
Number factors
Solution: Number factors
Minimum jumps to reach the end
Solution: Minimum jumps to reach the end
Minimum jumps with fee
Solution: Minimum jumps with fee
House thief
Solution: House thief
Longest Palindromic Subsequence
Solution: Longest Palindromic Subsequence
Longest Palindromic Substring
Solution: Longest Palindromic Substring
Count of Palindromic Substrings
Solution: Count of Palindromic Substrings
Minimum Deletions in a String to make it a Palindrome
Solution: Minimum Deletions in a String to make it a Palindrome
Palindromic Partitioning
Solution: Palindromic Partitioning
Longest Common Substring
Solution: Longest Common Substring
Longest Common Subsequence
Solution: Longest Common Subsequence
Minimum Deletions & Insertions to Transform a String into another
Solution: Minimum Deletions & Insertions to Transform a String into another
Longest Increasing Subsequence
Solution: Longest Increasing Subsequence
Maximum Sum Increasing Subsequence
Solution: Maximum Sum Increasing Subsequence
Shortest Common Super-sequence
Solution: Shortest Common Super-sequence
Minimum Deletions to Make a Sequence Sorted
Solution: Minimum Deletions to Make a Sequence Sorted
Longest Repeating Subsequence
Solution: Longest Repeating Subsequence
Subsequence Pattern Matching
Solution: Subsequence Pattern Matching
Longest Bitonic Subsequence
Solution: Longest Bitonic Subsequence
Longest Alternating Subsequence
Solution: Longest Alternating Subsequence
Edit Distance
Solution: Edit Distance
Strings Interleaving
Solution: Strings Interleaving
Contact Us
What is Dynamic Programming?
Table of Contents

Characteristics of Dynamic Programming

Overlapping Subproblems

Optimal Substructure Property

Top-down with Memoization

Bottom-up with Tabulation

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

Let's take the example of the Fibonacci numbers. As we all know, Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8, and they continue on from there.

If we are asked to calculate the nth Fibonacci number, we can do that with the following equation,

Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

As we can clearly see here, to solve the overall problem (i.e. Fib(n)), we broke it down into two smaller subproblems (which are Fib(n-1) and Fib(n-2)). This shows that we can use DP to solve this problem.

Characteristics of Dynamic Programming

Before moving on to understand different methods of solving a DP problem, let’s first take a look at what are the characteristics of a problem that tells us that we can apply DP to solve it.

Overlapping Subproblems

Subproblems are smaller versions of the original problem. Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem multiple times. Take the example of the Fibonacci numbers; to find the fib(4), we need to break it down into the following sub-problems:

Recursion tree for calculating Fibonacci numbers
Recursion tree for calculating Fibonacci numbers

We can clearly see the overlapping subproblem pattern here, as fib(2) has been evaluated twice and fib(1) has been evaluated three times.

Optimal Substructure Property

Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems. For Fibonacci numbers, as we know,

Fib(n) = Fib(n-1) + Fib(n-2)

This clearly shows that a problem of size 'n' has been reduced to subproblems of size 'n-1' and 'n-2'. Therefore, Fibonacci numbers have optimal substructure property.

Top-down with Memoization

In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This technique of storing the results of already solved subproblems is called Memoization.

We’ll see this technique in our example of Fibonacci numbers. First, let's see the non-DP recursive solution for finding the nth Fibonacci number:

Python3
Python3
. . . .

As we saw above, this problem shows the overlapping subproblems pattern, so let's make use of memoization here. We can use an array to store the already solved subproblems (see the changes in the highlighted lines).

Python3
Python3
. . . .

Bottom-up with Tabulation

Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we solve the problem "bottom-up" (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.

Tabulation is the opposite of Memoization, as in Memoization we solve the problem and maintain a map of already solved sub-problems. In other words, in memoization, we do it top-down in the sense that we solve the top problem first (which typically recurses down to solve the sub-problems).

Let's apply Tabulation to our example of Fibonacci numbers. Since we know that every Fibonacci number is the sum of the two preceding numbers, we can use this fact to populate our table.

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

Python3
Python3
. . . .

In this course, we will always start with a brute-force recursive solution, which is the best way to start solving any DP problem! Once we have a recursive solution then we will apply Memoization and Tabulation techniques.

Let's apply this knowledge to solve some of the frequently asked DP problems.

Introduction
Mark as Completed

Table of Contents

Characteristics of Dynamic Programming

Overlapping Subproblems

Optimal Substructure Property

Top-down with Memoization

Bottom-up with Tabulation