In this blog post we will discuss various dynamic programming questions. The idea is to have a same template to understand all the dynamic programming problems. All the problems that we discuss will be divided into four parts:-
- What is the question? (read * 2 times)
- Why this problem can be solved with the help of Dynamic Programming? (read once)
- What does dp[i][j] or dp[i] mean with respect to the question? (read once)
- What is the solution if the assumed dp array is to be constructed? (read once)
- How the dp[i] or dp[i][j] will be formulated? Along with the help of an example. (read twice)
- Variations to the questions
Once these algorithms are done, we will observe that even the new problems can be solved with the help of this template. I have used same terminology to make the questions easier.
1. Longest Common Subsequnce
QUESTION : Given two sequences, find the length of longest subsequence present in both of them. In the code given below we assume X,Y to be strings.WHY DP: Notice that given problem can be broken down as smaller chunk problem. Let us just take the first character of both the strings and compare them. Then we take the next character of string 1 and compare it with string 2 and so on.
DP[i][j]:
for the string s1[0..i] and string s2[0..j] what is the length of longest common subsequence with those specific substrings. Example let string 1 be "abcdefg" anf string 2 be "abcdgk"
SOLUTION: dp[n][m] (initialized as dp[n+1][m+1]
CODE:
https://github.com/vaibhavgeek/tompetitive/blob/master/dynamicProgramming/lcs.cpp
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
Variations:-
- Printing Longest Common Subsequence
- Longest Common Subsequence with at most k changes allowed
2. Maximum Sum Subarray
dp[i] = max(dp[i-1] + a[i] , a[i])
dp[i] = dp[i-1] + a[i] - a[i-k-1]
3. Longest Increasing Subsequence
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. if(arr[j] < arr[i])
dp[i] = max(dp[i], dp[j] + 1)
4. KnapSack Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property)
In this problem we define dp[i][j] as i value and for j knapsack capacity. That is for j capacity how much maximum value it can store.
if( j < wt[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j - wt[i]] + val[i] , dp[i-1][j]);
5. Coinchange Problem
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. if(j >= coin[i])
{
dp[i][j] = min(1 + dp[i][j-coin[i]] , dp[i-1][j]);
}
else
{
dp[i][j] = dp[i-1][j];
}5. Wordbreak Problem
Posts
