Dynamic Programming

Those who cannot remember the past are condemned to repeat it.

Dynamic Programming

Table of Contents

  • Introduction
  • Example – Fibonacci Number
  • Top Down and Bottom Up Approaches
  • Some Pointers
  • Problem Solving
    • Leetcode #70: Climbing Stairs
    • Leetcode #198: House Robber
    • Leetcode #746: Min Cost Climbing Stairs
    • Leetcode #62: Unique Paths
    • Leetcode #63: Unique Paths II
    • Leetcode #64: Minimum Path Sum
    • Leetcode #96: Unique Binary Search Trees
    • Leetcode #53: Maximum Subarray
    • Leetcode #300: Longest Increasing Subsequence
    • Leetcode #1143: Longest Common Subsequence
    • Leetcode #72: Edit Distance
  • Summary

Prefer Video over Text?

Watch the Dynamic Programming for Beginners series.

All that you need to know about Dynamic Programming

Introduction

Dynamic Programming… A topic that many are afraid of and a topic that is loved by interviewers. In all interview loops of the top tech companies, generally, at least one problem on dynamic programming gets asked and many candidates struggle in this round. It is a widely accepted fact that DP is one of the hardest topics to study or solve problems. In this blog post, we will go over everything that you need to solve DP problems and at the end of the post, I will let you decide whether to categorize DP as a hard topic, or a medium,  or an easy one. We are not only going to study the theory, but we will also discuss commonly asked interview problems. Wasting no time, let’s jump right in.

If you haven’t read my post on recursion and backtracking, I strongly encourage you to do so. Dynamic Programming builds on recursion and it is important that you feel comfortable with recursion. 

The idea behind solving dynamic programming problems is simple – remember what you have already solved and use the already computed solution in case you are solving the same problem again. In other words, solve one problem only once and remember the solution to it so that you can quickly provide the solution without the need to solve the problem again. This is all there is to know. And as you can see, it makes total sense. In the real world, when you face any difficulties, you remember the lessons and learnings so that you know how to deal with the problem if it arises the next time. A very simple example, if I ask you a simple question – what is 2 power 6. If you don’t know it instantly, you will quickly find it by multiplying 2, 6 times. 2, 4, 8, 16, 32, and 64. Now after 5 minutes if I ask you the same question again, will you do the multiplication again, or instantly say 64? The second time you were able to answer the question instantly because you had the answer in your memory. Your brain is super smart, we want to make the computer programs smart too. And that is done by dynamic programming.

Dynamic programming problems are a category of problems where it makes sense to remember the solutions to smaller problems that we solve along the way of solving the bigger problem. Formally, dynamic programming problems have two important properties –

  1. Optimal Substructure
    This simply means that if you solve smaller problems optimally, you can solve the bigger problem optimally.
  2. Overlapping Subproblems
    This is self-explanatory – there will be some smaller problems that you will need to solve multiple times along the way of solving the bigger problem. This immediately tells you to remember solutions to all smaller problems so that whenever the solution to the same problem is required again, you will immediately be able to answer it instead of computing it.

The uniqueness of the dynamic programming problems is that they are difficult to solve if you are thinking of the problem as one big problem. The moment you break the problem and see the above properties, it becomes a lot easier.

If this was a lot of theory, let’s see some problems and how they fit into the dynamic programming category.

Example – Fibonacci Number

The most commonly used example when explaining the dynamic programming – Fibonacci series. It is easiest to understand because of its very own recursive nature.

The nth Fibonacci number can be calculated as the addition of the previous two Fibonacci numbers. The first two numbers being 0 and 1.

F(n) = 0  _______________________ When n=1
     = 1  _______________________ When n=2
     = F(n-1) + F(n-2) __________ Otherwise

I assume you can easily write the recursive code for this problem. What I want to bring your attention to is the recursion tree. 

Fibonacci Number Recursion Tree Diagram
Fibonacci Number Recursion Tree Diagram

As you can see, to find the 6th Fibonacci number, we need to find the 5th and the 4th. Similarly, for the 5th, we need 4th and 3rd, and so on. If you look closely, we are repeatedly solving the same smaller problems. This is nothing but the “overlapping subproblems” property and hence we can categorize the problem as a dynamic programming problem.

From the above example, you can see – 

F(6) is computed once.
F(5) is computed once.
F(4) is computed 2 times.
F(3) is computed 3 times.
F(2) is referred to 5 times. (We have the F(1) and F(2) already).
F(1) is referred to 3 times. (We have the F(1) and F(2) already).

This shows you the exponential nature of the problem. For a small number like 100, it would be impossible to find the answer because of this. Repeatedly solving the same problem is wasteful and can be avoided by a simple idea of dynamic programming – remember what you solve. What if we keep a table where we write the answer to the problems that we have already solved. Whenever we start to solve a problem, we first refer to the table and only solve it if it is not there in the table already. It would completely change the game.

From visualization point of view, this is how it would look like –

Fibonacci Number using Dynamic Programming
Fibonacci Number using Dynamic Programming

And here is how our code will be –

class Solution {
public:
map<int, int> memory; // for storing precomputed answers.
int fibonacci(int n) {
if (memory.find(n) != memory.end()) { // if already exists.
return memory[n]; // just return the precomputed value.
}
// Find the n_th Fibonacci number and make a note of it in memory.
memory[n] = fibonacci(n-1) + fibonacci(n-2);
return memory[n];
}
int n_th_fibonacci(int n) {
memory[1] = 0; // base case that we already know.
memory[2] = 1; // base case that we already know.
return fibonacci(n); // find answer.
}
};

Top Down and Bottom Up Approaches

What we did above is simply adding a “memory” to our program. At any time it would check the memory first and then move forward to recursive calls if it does not find the answer in the memory. It will also make a note for a future reference. 

The above approach is one way to look at it. Another approach is to realize that for any number n, we will need the answer of n-1 and n-2. So instead of trying to find the answer for n directly,  we can first find the answers of n-1 & n-2 and then only go for finding the answer of n. That way, it’s easy to find the answer for n because we will already know the answer for n-1 and n-2. 

The difference between the two approaches is very small and both approaches are correct. The approach with which we solved the Fibonacci problem, we started with n and then tried to find the answers for n-1 and n-2 by making recursive calls. Hence it is called a “top-down approach”. On the other hand, the second approach we talked about, as you might have already guessed, is a “bottom-up approach”. In this approach, we try to find the answers for all smaller problems first and then only go for finding the answer to the larger problem.

We understood the “top-down” vs “bottom-up” approach, so let’s take a quick look at “memoization” vs “tabulation” techniques. Hint hint: See the respective order of the approaches and techniques.

In the top-down approach, we tried to remember the solutions to the problem as and when we figured out the solutions. We kept them into memory for future reference and that is why it is called “memoization”. Keep in memory i.e. remember what you have solved is memoization.

In the bottom-up approach, we find solutions to the problems in smaller to larger order which resembles maintaining a table of the problem and the corresponding solution. Hence it is called “tabulation”.

In short:
Top-down    —    Memory   —   Memoization
Bottom-up   —    Table        —   Tabulation

I didn’t show you the code for our Fibonacci problem, so let’s take a quick look at it as well.

class Solution {
public:
map<int, int> table; // for storing solutions of smaller problems.
int fibonacci(int n) {
for (int i=3; i<=n; i++) { // from smaller to larger problems.
// We go from smaller to larger, so it guarantees that
// values [i-1] and [i-2] exist in the table.
table[i] = table[i-1] + table[i-2];
}
return table[n]; // actual answer.
}
int n_th_fibonacci(int n) {
table[1] = 0; // base case that we already know about.
table[2] = 1; // base case that we already know about.
return fibonacci(n); // solve the problem.
}
};

Nothing different than what we already talked about. 

  • Some developers find the bottom-up easier while others find top-down easy.
  • Some developers think top-down to be more intuitive than bottom-up while others think otherwise.
  • For some problems, top-down is better fit while for others bottom-up is.
  • And of course, some like one approach over the other. 

As you can see, none of them is particularly hard. So, it’s best to know everything and use the right tool at the right time which can make writing the code and solving the problem, just a piece of cake.

Some Pointers

From the necessary knowledge point of view, this is all there is to know. Now comes the part of actually solving the problems and writing the code. We will look at some DP problems now, but before that, I want to give some pointers that would help you in identifying the problem as a dynamic programming problem and poking the problem to reach the solution.

  1. Don’t start writing code until you have solved the problem on paper. This applies to all problems, but especially for dynamic programming because you will need to draw the tree diagrams to understand the pattern, to see if there are problems that need to be solved multiple times. You should be able to write the solution in mathematical form as we did it for Fibonacci problem i.e. F(n) = 0  for n = 1, 1 for n = 2, and F(n-1)+F(n-2) otherwise. The moment you are able to write this mathematically, it is just a matter of time when you can write the code.
  2. Although I covered this in the previous point, just so I stress it enough – write the solution in a mathematical form first on paper before starting to write the code.
  3. The recursion-tree diagram will help you in identifying “overlapping subproblems” property.
  4. If possible write the recursive code and then convert to a memoized version. (The conversion won’t always be easy).
  5. List down what base cases are. What do you already know? For example, the first and the second Fibonacci numbers are 0 and 1 respectively, or the sum of an array of size 1 is the same as the element in the array.
  6. Once you know the base cases, see if you can solve the problem of size just larger than the base cases using the base cases you know.
  7. As I said earlier, it can be difficult to find the solution to a large problem on its own. Think if you can rather solve very small problems and then build on top of that.
  8. If you can use the problem of size n-1 to solve the problem of size n, then this confirms that it is a dynamic programming problem as this is nothing but an optimal substructure property. And this is the key to cracking the dynamic programming problems.
  9. There are many dynamic programming problems, but the patterns in those are very small in number. So you will definitely get better at identifying and solving such problems with the practice.

Problem Solving

Leetcode #70: Climbing Stairs

You want to find the number of ways to reach step N by taking 1 or 2 steps at a time.

There are only two actions you can do to reach step N.

  1. You will take 1 last step to reach the step N. So you must be at step N-1 so that you can take 1 step and reach N.
  2. You will take 2 steps at once to reach the step N. For that, you must be at step N-2.

Do you see something? 

  1. If you assume that you will take one step at the end, the number of ways in which step N can be reached is equal to the number of ways in which N-1 can be reached. Does it make sense? If there are P ways to reach N-1, you can always take 1 extra step after each possible way to reach N-1, so N can also be reached in P ways.
  2. Similarly, if you assume that you will take 2 steps at the end, the number of ways in which N can be reached is equal to the number of ways in which N-2 can be reached.

This is all we need to find the answer for the number of ways in which N can be reached. You guessed it right –

F(N) = F(N-1) + F(N-2)

Base conditions? We know the first step can only be reached in 1 way and the second step can be reached 2 ways i.e. directly reaching at 2 or 1+1.

So,

F(1) = 1 and F(2) = 2.

Converting the above function F into code is not a big deal. You can do it recursively with memoization or iteratively, bottom-up, with tabulation. The way in which we thought was a top-down approach. We started at N and wanted to reach there so we figured out that we need answers for N-1 and N-2.

The bottom-up way of thinking is as follows –

You know you can reach step 1 in 1 way and step 2 in 2 ways. To reach 3, you can either come from 2 (3-1) or come from 1 (3-2). Similarly for 4, either from 3 (4-1) or 2 (4-2), and so on. Here is the bottom up implementation –

class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
for (int i=3; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
// Note: Space complexity of this solution can be reduced to O(1) by using 2-3 variables instead of an array/vector.
// As this generates a Fibonacci series, you can use a relatively more complex but efficient way of finding Nth Fibonacci number instead of using the dynamic programming approach.
view raw Leetcode_0070.cpp hosted with ❤ by GitHub

(Hint hint: You have seen this code in the past, haven’t you? It can’t be a Fibonacci series code, can it be? :p)

Leetcode #198: House Robber

You are a robber who doesn’t want to rob two adjacent houses. Robbing each house gives you some money and of course you want to maximize that.

Top down –

Let’s say you must rob the house at N. You definitely can’t rob from house N-1. You can rob from N-2 and any houses before N-2. If you think about it, there is no point in skipping more than 2 houses i.e. robbing from N and skipping N-1, N-2, N-3 and directly robbing N-4 because you might as well rob N-2 because you are still not violating the condition (of not robbing two adjacent houses) and as long as N-2 has non-negative amount of money, you would like to take that. Draw some simple diagrams to realize this maybe.

Should you then rob the first valid house i.e. if you rob N, should you rob N-2 always? The answer is no. Because robbing N-3 instead of N-2 can be more profitable.

Hence what we want to do is pick a house whichever gives you higher profit. Hence the general formula becomes –

F(n) = money[n] + max(F(n-2), F(n-3))

Base conditions?

If there are no houses, you won’t get anything. If there is only one house to rob, you will always rob that. If there are two, you will pick the max of those two. 

F(0) = 0
F(1) = money[1]
F(2) = max(money[1], money[2])

Bottom up –

You know which house to rob if the number of houses are <= 2. If there are 3 houses, you can choose to rob the 2nd house in which case you can’t rob the 1st and the 3rd. Or you can choose to rob the 1st and the 3rd but not the 2nd. Similarly, for N=4, you can find the profitable way among robbing 2 or robbing 1 (you of course can not rob 3), and so on.

class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
if (n==1) {
return nums[0];
}
if (n==2) {
return max(nums[0], nums[1]);
}
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = nums[0];
dp[2] = max(nums[0], nums[1]);
for (int i=3; i<=n; i++) {
dp[i] = nums[i-1] + max(dp[i-2], dp[i-3]);
}
return max(dp[n], dp[n-1]);
}
};
// Note: Space complexity of this solution can be reduced to O(1) by using 3-4 variables instead of an array/vector.
view raw Leetcode_0198.cpp hosted with ❤ by GitHub

Leetcode #746: Min Cost Climbing Stairs

Now you want to minimize the cost, climbing each stair costs you something and you can climb 1 or 2 stairs at a time. Very similar to the previous two problems. 

The cost for 0th step is cost[0] and for the 1st step is cost[1].

You can choose to go to step 2 from 0 by climbing 2 steps or from 1 by climbing 1 step. For 3, you can choose to come from step 1 or 2, whichever is cheaper, and so on.

So, 

F(0) = cost[0]
F(1) = cost[1]
F(N) = cost[N] + min(cost[N-1], cost[N-2])

Easily, the solution can be implemented as –

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
if (n == 0) {
return 0;
}
if (n == 1) {
return cost[0];
}
vector<int> dp(n);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i=2; i<n; i++) {
dp[i] = cost[i]+min(dp[i-1], dp[i-2]);
}
return min(dp[n-1], dp[n-2]);
}
};
// Note: Space complexity of this solution can be reduced to O(1) by using 3-4 variables instead of an array/vector.
view raw Leetcode_0746.cpp hosted with ❤ by GitHub

Leetcode #62: Unique Paths

You want to move from (0, 0) to (n-1, m-1) by taking right and down turns. 

Say F(i, j) denotes the number of ways in which you can move from (0, 0) to (i, j).

Quickly you can tell, 

F(0, 0) = 1

At any cell (i, j) there are only two ways you can reach that cell from the previous cell i.e. you can be at (i-1, j) and you go downwards to reach (i, j), or you can be at (i, j-1) and go right to reach (i, j).

This simply tells you that the number of ways of reaching (i, j) is simply the number of ways in which you can reach (i, j-1) and (i-1, j).

So,

F(i, j) = F(i-1, j) + (i, j-1)

If n = 1 i.e. number of rows are 1, then there is only one way to reach any cell from (0, 0) i.e. by going in the right direction.

F(0, j) = 1  ... for j = 0 to m-1.

Similarly, if m = 1, columns = 1, so you can only go downwards.

F(i, 0) = 1  ... for i = 0 to n-1.

You have got everything to code this up.

class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(n, vector<int>(m));
for (int i=0; i<n; i++) {
dp[i][0] = 1;
}
for (int j=0; j<m; j++) {
dp[0][j] = 1;
}
for (int i=1; i<n; i++) {
for (int j=1; j<m; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
};
view raw Leetcode_0062.cpp hosted with ❤ by GitHub

Leetcode #63: Unique Paths II

This is very similar to the problem above but now there are obstacles in the path. If changes the solution slightly. As we can not pass through obstacles, we can never reach the obstacle cells.

This means that,

F(i, j) = 0 for all (i, j) where there is an obstacle.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
vector<vector<int>> dp(n, vector<int>(m));
for (int i=0; i<n; i++) {
if (obstacleGrid[i][0]) {
dp[i][0] = 0;
} else {
dp[i][0] = dp[i-1][0];
}
}
for (int j=0; j<m; j++) {
if (obstacleGrid[0][j]) {
dp[0][j] = 0;
} else {
dp[0][j] = dp[j-1][0];
}
}
for (int i=1; i<n; i++) {
for (int j=1; j<m; j++) {
if (obstacleGrid[i][j]) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[n-1][m-1];
}
};
view raw Leetcode_0063.cpp hosted with ❤ by GitHub

Leetcode #64: Minimum Path Sum

Very similar to the above two problems. Here, we want to find the path from (0, 0) to (n-1, m-1) that has the minimum sum. The previous question asked for a number of ways. It doesn’t change the way we approach the problem.

Say, F(i, j) is the minimum sum of the path from (0, 0) to (i, j).

You can easily tell-

F(0, 0) = grid[0][0]

We can only go in the right or down direction, so there are only two ways of reaching the cell (i, j) – either from (i-1, j) or from (i, j-1). We will of course choose the smaller one. Either way, because you are reaching the cell (i, j), you must add the cost to the sum.

Hence,

F(i, j) = min(F(i-1, j), F(i, j-1)) + grid[i][j].

If the number of rows is 1, there is only one path i.e. going right.

F(0, j) = F(0, j-1) + grid[0][j]  .... for all j = 1 to m-1.

If the number of columns is 1, there is only one path i.e. going downwards.

F(i, 0) = F(i-1, 0) + grid[i][0]  .... for all i = 1 to n-1.

The code is not very different either.

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m));
dp[0][0] = grid[0][0];
for (int i=1; i<n; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j=1; j<m; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i=1; i<n; i++) {
for (int j=1; j<m; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
};
view raw Leetcode_0064.cpp hosted with ❤ by GitHub

Leetcode #96: Unique Binary Search Trees

This is a very interesting problem. You want to find out the number of unique binary search trees using numbers 1 to N.

Let’s say F(N) is the number of unique binary search trees you can form using N distinct numbers.

Think about it – if you choose a number K where 1 <= K <= N and make it root. What do you know for certain? The number of nodes in the left subtree are going to be K-1 (from 1 to K-1). The number of nodes in the right subtree will be N-K (from K+1 to N).

Now, the number of ways of forming unique binary search trees in the left subtree will be F(K-1). Similarly, for the right subtree it will be F(N-K). Hence the total unique binary search trees with N nodes and K as the root will be all combinations of left subtrees with right subtrees i.e. F(K-1) * F(N-K).

But K can be any root from 1 to N, so we will have to repeat the process for all possible values of K and add them together.

This makes the foundation for the answer.

F(N) = sum(F(K-1) * F(N-K)) ......... for K = 1 to N.

Base conditions?

If N = 0, there is only one way i.e. an empty tree.
If N = 1, again, only one tree is possible.

So, 

F(0) = 1
F(1) = 1

Coding this is trivial –

class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for (int i=2; i<=n; i++) {
int sum = 0;
for (int k=1; k<=i; k++) {
sum += dp[k-1]*dp[i-k];
}
dp[i] = sum;
}
return dp[n];
}
};
view raw Leetcode_0096.cpp hosted with ❤ by GitHub

Note: Beyond this point, it would really help to have a pen and a paper to work through a couple of examples.

Leetcode #53: Maximum Subarray 

You want to find the subarray with maximum sum.

If there were no negative numbers, we would simply choose the entire array and sum it. Negative numbers make it a more interesting problem to solve. 

We can break down the problem into two smaller problems. 

Part 1: For each index `i`, find the maximum sum subarray that ends at index `i`. The subarray must include the element at index `i`. So the subarray can start at index 0, 1, or `i-1`, or even `i` and it ends at index `i`. We only care about the subarray that yields maximum sum out of all those possibilities. Let’s denote the maximum sum subarray ending at index `i` as F(i). We repeat this procedure for all indices i = 0 to N-1. (Subarray can start at any index `j` <= `i` and `j` >= 0).

Part 2: Once we have all values of F(i), we can just find the maximum value among all F(i) and that will be our answer.

You can easily tell,

F(0) = arr[0]

For F(1)

Maximum Sum of subarray that ends at index 1. We must take the value arr[1] into account. But we have a choice here – the subarray can start at index 0 or index 1. If the maximum sum of subarray ending at index 0 is positive, adding that value into arr[1] will definitely be better than not adding it i.e. arr[1] + X >= arr[1] if X >= 0. 

In other words,

For F(1), if F(0) is a positive number, then you will definitely want to add it to maximize the sum of the subarray that ends at index 1. If F(0) is negative, you will want to ignore that because it reduces the maximum sum possible for subarray ending at index 1. You will rather want to just take arr[1] in that case. 

i.e.

F(1) = F(0) + arr[1]    ...  if F(0) >= 0
F(1) = arr[1]                ...  if F(0) < 0. 

So in general, 

F(i) = arr[i] + F(i-1) .... if F(i-1) >= 0 
         = arr[i]                 .... if F(i-1) < 0

which is equivalent to,

F(i) = arr[i] + max(0, F(i-1))

Once you have all values of F(i), final answer is –

result = max(F(i)) for i=0 to N-1.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
vector<int> dp(n);
dp[0] = nums[0];
for (int i=1; i<n; i++) {
dp[i] = nums[i] + max(0, dp[i-1]);
}
return *max_element(dp.begin(), dp.end()); // max in the dp vector.
}
};
// You can easily reduce the space complexity by using 1-2 variables instead of an entire vector/array.
view raw Leetcode_0053.cpp hosted with ❤ by GitHub

Leetcode #300: Longest Increasing Subsequence

Similar to the previous problem, if you know the lengths of longest increasing subsequences that end at index `i` (must include element at index `i`) for each index i = 0 to N-1, can you find the longest increasing subsequence of the original array? Yes, easy. You will just take the max of all those lengths.

Precisely, let’s say – F(i) is the length of longest increasing subsequence that ends at index `i`.

You can easily tell, F(0) = 1 because there is only one element to consider.

To find F(1), we will need to check if arr[1] > arr[0]. If it is true, then we can safely include “all the elements in a longest increasing subsequence that ends at 0” – into a subsequence that ends at arr[1] without violating the condition – “subsequence must be increasing”. (Maybe consider an example to understand this.)

If arr[1] < arr[0], then we can’t take arr[0] into the longest increasing subsequence that ends at arr[1] because otherwise the subsequence won’t be increasing anymore.

Similarly for 2, we will check whether arr[0], arr[1] are smaller than arr[2]. 

In general, if there are multiple elements arr[j] that are smaller than arr[i] were j < i, we can take whichever is longer. (I understand it is getting a bit complex to grasp but have an example for easier understanding and keep reading).

Formally, 

F(0) = 1
F(i) = 1              ... if for all j = 0 to i-1,
                          arr[j] >= arr[i]
     = 1 + (max(F(j)) ... for all j = 0 to i-1 
                          where arr[j] < arr[i])

Implementing this in code is not as difficult as explaining it –

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
vector<int> dp(n);
dp[0] = 1;
for (int i=1; i<n; i++) { // Find the length of the longest increasing
// subsequence that ends at index i.
int maxLengthSoFar = 0; // Length of the longest increasing subsequence that
// ends at some index j < i and has the element
// nums[j] < nums[i].
for (int j=0; j<i; j++) { // For all previous elements.
if (nums[j] < nums[i]) { // if the element is smaller.
maxLengthSoFar = max(maxLengthSoFar, dp[j]);
}
}
dp[i] = maxLengthSoFar+1;
}
return *max_element(dp.begin(), dp.end());
}
};
view raw Leetcode_0300.cpp hosted with ❤ by GitHub

Leetcode #1143: Longest Common Subsequence

Find the longest common subsequence between string1 and string2.

I realize explaining with code can be easier than the theoretical explanation. So I will keep the explanation short.

Let’s define F(i, j) as the length of longest common subsequence between the string a and string b where a is a substring of string1 starting at index 0 and ending at `i` while b is a substring of string2 starting at index 0 and ending at `j`.

You can easily tell, 

F(0, 0) = 1  .... if string1[0] == string2[0].
        = 0  .... otherwise.

Similarly, 

F(0, j) = 1           .... if string1[0] == string2[j]
                      // the character is common.
        = F(0, j-1)   .... otherwise   
                      // the character is not common,
                      // so just carry forward the
                      // past result.

F(i, 0) = 1           .... if string1[i] == string2[0]
                      // the character is common.
        = F(i-1, 0)   .... otherwise   
                      // the character is not common,
                      // so just carry forward the
                      // past result.

And in general,

F(i, j) = 
  max
    (
      F(i-1, j),       // ignore the string1[i].
      F(i, j-1),       // ignore the string2[j].
      F(i-1, j-1) + 1  // string1[i] == string2[j]
    )

Other way to think about this is –

If you know the answers from all F(x, y), where x<i and y<j, can you use those answers for finding the answer for F(i, j). If we can use the answers of subproblems, you can find the final answer too because the final answer would just be F(N, M) where N is the length of string1 and M is the length of string2.

The only time length of common subsequence increases is when the `i`th and the `j`th character of string1 and string2 match each other and hence we can add 1 to the answer for substrings excluding both of these characters.

Checkout the code which might be easier to understand.

class Solution {
public:
int longestCommonSubsequence(string string1, string string2) {
int n = string1.size();
int m = string2.size();
vector<vector<int>> dp(n, vector<int>(m));
dp[0][0] = string1[0] == string2[0];
for (int i=1; i<n; i++) {
dp[i][0] = string1[i] == string2[0] ? 1 : dp[i-1][0];
}
for (int j=1; j<m; j++) {
dp[0][j] = string1[0] == string2[j] ? 1 : dp[0][j-1];
}
for (int i=1; i<n; i++) {
for (int j=1; j<m; j++) {
dp[i][j] = max({
dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1] + (string1[i]==string2[j])
});
}
}
return dp[n-1][m-1];
}
};
// With clever tricks, the code size can be reduced.
// Also, space complexity can be reduced to O(n) instead of O(n^2).
view raw Leetcode_1143.cpp hosted with ❤ by GitHub

Leetcode #72: Edit Distance

You want to convert a word1 to a word2 with insertion, updation and deletion operations.

Lets say, n and m are the lengths of word1 and word2 respectively. 

Say word1 can also be denoted as word1[0 .. n-1] i.e. from 0th index to (n-1)th index. Similarly, word2 is the same as word2[0 .. m-1]

Let’s say you know the number of operations required to convert –

  1. from word1[0 .. n-1] to word2[0 .. m-2]
  2. from word1[0 .. n-2] to word2[0 .. m-1]
  3. from word1[0 .. n-2] to word2[0 .. m-2]

Can you use the above answers to find the answer for converting from word1[0 .. n-1] to word2[0 .. m-1]?

The answer is simple – 

  1. If you want to convert word1[0 .. n-1] to word2[0 .. m-1] using (a) i.e. word1[0 .. n-1] to word2[0 .. m-2], there is only one way of doing it and it is by inserting the last character i.e. a character that is at word2[m-1].
    For example, say, you know the number of operations required for converting “abcd” to “efg”. You want to know the number of operations for converting “abcd” to “efgh”. You can simply add one ‘h’ to “abcd”. (Adding ‘h’ to “abcd” will make it “abcdh”. You already know the conversion “abcd” –> “efg”. So replacing “abcd” by “efg” in “abcdh” makes it “efgh” which is what we wanted.)
  2. If you want to convert word1[0 .. n-1] to word2[0 .. m-1] using (b) i.e. word1[0 .. n-1] to word2[0 .. m-2], there is only one way of doing it and it is by removing the character that is at word1[n-1].
    For example, say, you know the number of operations required for converting “abc” to “efgh”. You want to know the number of operations for converting “abcd” to “efgh”. You can simply remove the last ‘d’ from “abcd”. (Removing last ‘d’ from “abcd” makes it “abc”. You already know the conversion “abc” –> “efgh”, so replace “abc” by “efgh” in “abc” and you get the desired “efgh”.
  3. If you want to convert word1[0 .. n-1] to word2[0 .. m-1] using (c) i.e. word1[0 .. n-2] to word2[0 .. m-2], there is only one way of doing it and it is by updating a character that is at word1[n-1] by word2[m-1]. But if the characters are the same, you won’t have to perform that operation.
    For example, say, you know the number of operations required for converting “abc” to “efg”. You want to know the number of operations for converting “abcd” to “efgh”. You can simply update the last ‘d’ from “abcd” by one ‘h’. (Updating last ‘d’ from “abcd” to ‘h’ makes it “abch”. You already know the conversion “abc” –> “efg”, so replace “abc” by “efgh” in “abch” and you get the desired “efgh”.

At the end, you will choose the cheapest (fewer number of operations) one out of the above 3 ways.

Lets define F(i, j) as the cost of converting a string1 to string2 where string1 is formed by taking initial `i` number of characters from word1 and string2 is formed by taking initial `j` number of characters from word2.

We can say, in general –

F(i, j) = 
  min( 
    1 + F(i-1, j),   // Delete i-th character from word1.
    1 + F(i, j-1),   // Insert j-th character from word2.
    0 + F(i-1, j-1), // No cost if word1[i]==word2[j].
    1 + F(i-1, j-1)  // Update if word1[i]!=word[j].
  )

Base cases are pretty easy –

Say word1 is an empty string and we want to convert it to word2. The only option is to insert all characters from word2 into word1. Each insertion costs 1 operation, so –

F(0, j) = j ___________ for j = 0 to m

Similarly, if word2 is empty, the only option to convert from word1 to word2 is by deleting all characters from word1. Each deletion costs 1.

F(i, 0) = i ___________ for i = 0 to n

Now we have everything we need to build up the solution.

class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1));
for (int i=0; i<=m; i++) {
dp[0][i] = i;
}
for (int i=0; i<=n; i++) {
dp[i][0] = i;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
dp[i][j] = min(
{
dp[i-1][j-1] + (word1[i-1] != word2[j-1]),
dp[i-1][j] + 1,
dp[i][j-1] + 1
}
);
}
}
return dp[n][m];
}
};
view raw Leetcode_0072.cpp hosted with ❤ by GitHub

As an extension to this problem, one exercise – How would the code change if there is a different cost associated (instead of simply 1 as in above question) with different operations (insert, update, delete). How will you change the code? Let me know in the comments.

Summary

It was a long post and towards the end it got difficult to understand too. It is normal, I wouldn’t say DP is easy. Some problems are not very difficult to tackle, but sometimes it does get complex. We started with the dynamic programming concept, its importance and two key properties of dynamic programming problems – Overlapping Subproblems and Optimal Substructure. We discussed the top-down and bottom-up approach along with the difference between memoization and tabulation. Before shifting gears towards problem solving, we discussed some pointers to keep in mind. And finally we solved a few problems. 

There was a common theme among those problems. We broke each problem into subproblems and built up a general formula to solve the problem using solutions to subproblems. Base conditions were not so difficult to recognize. The most critical part is to understand how to break the problem in a useful way. This will come with more practice. The way I think is – how to solve a problem of size 2 using solutions to the problem of size 1, size 3 using size 1, size 2 and so on. Another approach I take is to assume solutions to all problems of smaller size are available and use them to solve the current problem at hand. Your mileage may vary and you may like one way vs the other or you might discover a unique way. I would be eager to know what works for you. 

What are your thoughts about dynamic programming? Do you feel more confident solving DP problems now? What new things did you learn? What is still unclear? What problem are you still struggling with? What problems were you struggling with but now feel empowered to tackle? Let me know everything in the comments and I will certainly be curious to know. 

Don’t forget to like, share the post and subscribe to the blog.

Happy coding!


Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s