Problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. The problems are usually solved in bottom-up manner, were smaller sub-problems are solved first, then the larger sub-problems are solved from them.
Memoization Matrix usually has the column with increasing number from 0 to final result, while the row has the elements which needs to selected for the optimal solution. The first column (and sometimes row) has the 0th column which is a hypothetical condition providing initial values with the matrix.
Levenshtein Distance
Determine the minimum edit distance for converting one string to another string
The Levenshtein distance is a string metric for measuring the difference between two sequences. It is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. Here we first create a matrix with Source String as the columns while Destination String as rows. If the row and column character are same then no operation is needed and we directly copy the previous value of the diagonal cell as it is. If the row and column character is different then we find the minimum previous value from the top, side and diagonal, add 1 to it to get the final value as below.
Character Operations: Replace, Delete, Insert.
Below is the code for Levenshtein Distance.
static void editDP(String s1, String s2)
{
int l1 = s1.length();
int l2 = s2.length();
int[][] DP = new int[l1 + 1][l2 + 1];
// initilize by the maximum edits possible
for (int i = 0; i <= l1; i++)
DP[i][0] = i;
for (int j = 0; j <= l2; j++)
DP[0][j] = j;
// Compute the DP matrix
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
// if the characters are same
// no changes required
if (s1.charAt(i - 1) == s2.charAt(j - 1))
DP[i][j] = DP[i - 1][j - 1];
else {
// minimu of three operations possible
DP[i][j] = min(DP[i - 1][j - 1],
DP[i - 1][j], DP[i][j - 1])
+ 1;
}
}
}
}
Coin Change Problem
When given coins of different denominations and a total amount, find out the number of combinations that make up that amount. Here the assumption is that there are unlimited supply of given coin denominations.
In the below table shows the P(n) for each number, which is the Number of ways representing an Integer as addition of positive Integers.
| n | Ways | P(n) |
|---|---|---|
| 1 | (1) | 1 |
| 2 | (2), (1+1) | 2 |
| 3 | (3), (2+1), (1+1+1) | 3 |
| 4 | (4), (3+1), (2+2), (2+1+1), (1+1+1+1) | 5 |
Lets see below example
Amount = 12
Coins = {1, 2, 5}
ForEach Coin in the given coin denominations i.e. {1, 2, 5}
If Amount >= Coin then
Combinations[Amount] += Combinations[Amount - Coin]
First initialize the Combinations array with 0 value for all elements.
Combinations when Coin is 1
Set Combinations[0] = 1 when coin is 0, which means using coin 0 to achieve amount 0 there is only 1 combination.
Then we use the above logic to determine the next value of the combination when coin is 1 and amount is 1.
Combinations[1] = Combinations[1-1] + Combinations[1] = Combinations[0] + Combinations[1] = 1 + 0 = 1
Similarly,
Combinations[2] = Combinations[2-1] + Combinations[2] = Combinations[1] + Combinations[2] = 1 + 0 = 1
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Combinations when Coin is 2
When Amount is 0 or 1 and Coin is 2, the condition (Amount >= Coin) becomes false, so we skip for Amounts 0 and 1.
When Amount is 2 and Coin is 2, we have,
Combinations[2] = Combinations[2-2] + Combinations[2] = Combinations[0] + Combinations[2] = 1 + 1 = 2
The original value of Combinations[2] was 1 from above.
Similarly when Amount is 3 and Coin is 2, we have,
Combinations[3] = Combinations[3-2] + Combinations[3] = Combinations[1] + Combinations[3] = 1 + 1 = 2
Similarly when Amount is 4 and Coin is 2, we have,
Combinations[4] = Combinations[4-2] + Combinations[4] = Combinations[2] + Combinations[4] = 2 + 1 = 3
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 7 |
Combinations when Coin is 5
When Amount is 0 to 4 and Coin is 5, the condition (Amount >= Coin) becomes false, so we skip Amounts 0 and 4.
When Amount is 5 and Coin is 5, we have,
Combinations[5] = Combinations[5-5] + Combinations[5] = Combinations[0] + Combinations[5] = 1 + 3 = 4
Similarly when Amount is 6 and Coin is 5, we have,
Combinations[6] = Combinations[6-5] + Combinations[6] = Combinations[1] + Combinations[6] = 1 + 4 = 5
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 | 13 |
int change(int amount, int[] coins) {
int[] combinations = new int[amount + 1];
combinations[0] = 1;
for(int coin : coins) {
for(int i = 1; i < combinations.length; i++) {
if(i >= coin) {
combinations[i] += combinations[i - coin];
}
}
}
}
Longest Common Subsequence (LCS) Problem
Longest Common Subsequence Problem is to find the common subsequences but are not required to occupy consecutive positions with the original sequences.
For example, consider the following sequences, A and B
A = bqdrcvefgh
B = abcvdefgh
Here the length of LCS is 7,
LCS are bdefgh and bcvefgh
We first construct a matrix with columns as characters of string A and rows as characters of string B.
- If one of the string is empty or both the strings are empty then the length of the longest common subsequence is 0, hence we put zero for both the empty character row and empty character column.
- When the row character matches with the column character for the cell, then take the previous diagonal value in the matrix and add 1 since there is a match, to get the final value of the cell.
- When the row character does not match with the column character for the cell, then take the maximum between the above cell and the left cell, to get the final value of the cell.
int longestCommonSubsequence(String A, String B) {
int m = A.length(), n = B.length();
int[][] table = new int[m+1][n+1];
for(int i = 0; i <= m; i++) {
table[i][0] = 0;
}
for(int j = 0; j <= n; j++) {
table[0][j] = 0;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(A.charAt(i - 1) == B.charAt(j - 1))
table[i][j] = table[i - 1][j - 1] + 1;
else
table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
}
}
return table[m][n];
}
Subset Sum Problem
Given a set of positive integers and an integer s, find if there is any non-empty subset whose sum is s.
For example set = { 1, 2, 7, 5 }
sum = 8 has subset { 1, 2, 5 }
sum = 4 has no subset
First the given set is sorted in ascending order.
Logic:
Since this is a dynamic programming problem we create a matrix with columns as 0 incrementing by 1 till the sum s. The rows are each element in the example set in a sorted order.
Truth Value = (Truth Value by Excluding New Value) OR (Truth Value by Including New Value)
Truth value by excluding the new value in the current cell comes from the value of upper cell within the matrix.
Truth value by including the new value in the current cell comes from getting the cell value of previous/upper row and the column equal to (sum - new value of the row) within the matrix.
Finally, we return true if we get subset by including or excluding current item else we return false.
To find the subset which gives the sum s, we go to the last cell and backtrack to check were the True value is coming from. If value in the cell above it is False, then it means current cell has become True after including the current element. So include the current element and check for the sum = sum – current element.
public static boolean subSetDP(int[] A, int sum) {
boolean[][] solution = new boolean[A.length + 1][sum + 1];
// if sum is not zero and subset is 0, we can't make it
for(int i=1; i<=sum; i++){
solution[0][i]=false;
}
// if sum is 0 the we can make the empty subset to make sum 0
for(int i=0; i<=A.length; i++){
solution[i][0]=true;
}
// do for ith item
for(int i=1; i<=A.length; i++){
// consider all sum from 1 to sum
for(int j=1; j<=sum; j++){
// don't include ith element if j-array[i-1] is negative
if(A[i-1] > j) {
//first copy the data from the top
solution[i][j] = solution[i-1][j];
}
else {
// find subset with sum j by excluding or including the ith item
solution[i][j] = solution[i-1][j] || solution[i-1][j - A[i-1]];
}
}
}
return solution[A.length][sum];
}
Partition Problem
Given a set of positive integers, find if it can be divided into two subsets with equal sum.
Example Set S = {3,1,1,2,2,1}
We can partition S into two partitions each having sum 5.
S1 = {1,1,1,2}
S2 = {2,3}
Another solution could be,
S1 = {3,1,1}
S2 = {2,2,1}
// Return true if there exists a subset of array[0..n) with given sum
private bool subsetSum(int arr[], int n, int sum)
{
// T[i][j] stores true if subset with sum j can be attained with
// using items up to first i items
bool T[n + 1][sum + 1];
// if 0 items in the list and sum is non-zero
for (int j = 1; j <= sum; j++)
T[0][j] = false;
// if sum is zero
for (int i = 0; i <= n; i++)
T[i][0] = true;
// do for ith item
for (int i = 1; i <= n; i++)
{
// consider all sum from 1 to sum
for (int j = 1; j <= sum; j++)
{
// don't include ith element if j-arr[i-1] is negative
if (arr[i - 1] > j)
T[i][j] = T[i - 1][j];
else
// find subset with sum j by excluding or including the ith item
T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]];
}
}
// return maximum value
return T[n][sum];
}
// Partition problem - Return true if given array arr[0..n-1] can
// be divided into two subsets with equal sum
public bool partition(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// return true if sum is even and array can can be divided into
// two subsets with equal sum
return !(sum & 1) && subsetSum(arr, n, sum/2);
}
0/1 Knapsack Problem
We are given a set of items, each with a weight and a value (or profit) and need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The 0/1 indicates that the item can either be selected or not selected, i.e. items are indivisible.
Sum of the Weights <= Total Weights
Sum of the value should be maximum
Consider the below example were we have items {a, b, c, d, e} with weights and values as below. We need to in the subset with maximum sum of value were sum of their weights should be equal to or less then 9. The quantity of all the items is 1. We create the matrix as below, with the columns as increasing number of weights aka Sum of weights from 0 to the total weight. The rows of the matrix are the sorted using item values.
| weight | value | |
|---|---|---|
| a | 1 | 1 |
| b | 3 | 4 |
| c | 4 | 5 |
| d | 5 | 7 |
| e | 2 | 4 |
| item | value | weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| e | 4 | 2 | 0 | 1 | 4 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| b | 4 | 3 | 0 | 1 | 4 | 5 | 5 | 8 | 9 | 9 | 9 | 9 |
| c | 5 | 4 | 0 | 1 | 4 | 5 | 5 | 8 | 9 | 10 | 10 | 13 |
| d | 7 | 5 | 0 | 1 | 4 | 5 | 5 | 8 | 9 | 11 | 12 | 13 |
We cannot achieve the zero weight, using the weights of any items so entire column is assigned the value 0. For column with weight 1, since item a which has weight 1 can contribute in forming the sum of the weights from 1 to 9, we add 1 to entire row. Now we follow below logic to determine the current value of the cell,
1) If item weight <= sum of weights,
value = maximum of(value by excluding the new item, value by including the new item)
To calculate the value by including the new item, we add
- value of the new item (not the weight)
- value from above row and the column (sum of weights in column - current item's weight).
2) If item weight > sum of the weights, copy the value from the above cell.
Use backtracking to determine from were the final value of 13 came to determine the weights or the items included in the result collection.
private int knapSack(int sumWeight, int weights[], int values[]) {
int n = values.length;
// K[i][j] stores the maximum value that can be attained with
// weight less than or equal to j using items up to first i items
int K[][] = new int[n + 1][sumWeight + 1];
for (int j = 0; j <= sumWeight; j++) {
K[0][j] = 0;
}
for (int i = 1; i<= n; i++) {
// consider all weights from 0 to maximum capacity sumWeight
for (int j = 0; j<= sumWeight; j++) {
// don't include ith element if j-weights[i-1] is negative
if (weights[i-1] > j)
K[i][j] = K[i-1][j];
else
// find max value by excluding or including the ith item
K[i][j] = Math.max(K[i-1][j], K[i-1][j-weights[i-1]] + values[i-1]);
}
}
return K[n][sumWeight];
}
Rod Cutting Problem
Given a rod of length n and list of pieces of rod of length i where 1 <= i <= n, find the optimal way to cut the rod into smaller rods in order to maximize the profit.
Rod of length = 5
lengths of pieces = {1, 2, 3, 4}
profits of pieces = {2, 5, 7, 8}
If we cut the rod in the given lengths of piece, then profit of each piece is given in corresponding profits set. The rod has to be cut in such a way that we get the maximum profit.
We create the memoization matrix, with column as total length of from 0 to length of the rod, and rows as length of each piece given in the set. Each cell has the profit value for the corresponding piece with the length.
The piece with length 0 is hypothetical condition, hence, entire row's values is 0.
Also if we want to make the total length of 0 for column with sum of length as 0, none of the piece from length 1 to 4 satisfy the condition, hence all entries there are 0.
If we have a piece of length 1 and we want total length to be 1, we need only 1 piece with length 1 to achieve that, hence the profit value of piece 1 is added to the corresponding cell. Similarly, to achieve the total length of 2, we need two pieces of length 1, hence we add profit value of piece 1 twice to corresponding cell. Similar goes for columns 3,4 and 5 with row of piece length 1.
When the row piece length is greater than column total length we copy the cell value from upper row. If the row piece length is less than or equal to column total length, then we use the below logic. Profit by including new piece is,
(Profit of current piece) +
(Profit of cell with column as (Current Total length - Current piece length) in current row).
Profit = max (Profit by excluding new piece, Profit by including new piece)
| profit | length | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 2 | 4 | 6 | 8 | 10 |
| 5 | 2 | 0 | 2 | 5 | 7 | 10 | 12 |
| 9 | 3 | 0 | 2 | 5 | 9 | 11 | 14 |
| 6 | 4 | 0 | 2 | 5 | 9 | 11 | 14 |
// n is the maximum length of the rod
public int rodCut(int[] price, int n)
{
// T[i] stores maximum profit achieved from rod of length i
int[] T = new int[n + 1];
T[0] = 0;
// consider rod of length i
for (int i = 1; i <= n; i++)
{
// divide the rod of length i into two rods of length j
// and i-j each and take maximum
for (int j = 0; j < i; j++) {
T[i] = Math.max(T[i], price[j] + T[i - (j + 1)]);
}
}
// T[n] stores maximum profit achieved from rod of length n
return T[n];
}
Word Break Problem
Given a string and a dictionary of words, determine if string can be segmented or split into a space-separated sequence of one or more dictionary words.
E.g. dictionary[] = { "this", "th", "is", "famous", "break", "b",
"r", "e", "a", "k", "br", "bre", "brea", "ak", "problem"}
string = "Wordbreakproblem"
