Category Archives: Dynamic Programming

Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination.

For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total.

Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count which takes in the parameter amount N, and the index of current denomination, we can have pseudo code like this

Count(N, index)

  • Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominations
  • Base case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none.
  • Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term), or take the current denomination(second term) and recurse accordingly.

Since this recursive method solves the same problem multiple times, we can think of a dynamic programming solution for this problem. In dynamic programming, we solve the smaller sub problems first and use their results in solving bigger sub problems. We store the results in a table. Lets create a table[N+1][M] where N is the amount, and M is the denomination count.

  • table[0][j] = 1, Only one way to make 0.
  • table[i][0] = 1 if N is divisible by D[0], otherwise 0
  • table[i][j] = table[i][j-1] if D[j] > i
    = table[i][j-1] + table[i- D[j]][j]

Here is the Java code which implements the above approach.

Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?

For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements. 

The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.

Can we do better than this?

Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.
 

In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.
 

In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.

Let us calculate this array for the above example
 

Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length     = 0 0 0 0 0 0

Iteration 2:
Cumulative Sum = _ 0 -1 2 0 4
Max Length     = 0 1  0 0 4 0

Iteration 3:
Cumulative Sum = _ _ -1 2 0 4
Max Length     = 0 1  0 0 4 0

and so on.

At the end of all this, maximum of this array contains the result.

Here is the C++ code.

Minimum number of characters to insert to make a palindrome

Given a string, how do you find the minimum number of characters to insert to make it a palindrome?
For example given a string “abbc”, the number of characters to insert is 2, and the resulting palindrome is “cabbac”
Take another example “abc”, we need to insert two characters at a minimum to make it a palindrome “abcba”
If the given string is already a palindrome, the result is 0.

Let us analyze the problem to find out a solution. Given a string, we have two possible cases
  • Case 1:The first and last characters are equal. In this case, the minimum number of characters to insert depends on the sub-string between the first and last characters. 
    • For example consider the string “abca”, the value depends on the sub-string “bc”
  • case 2:The first and last characters are not equal. In this case, we have to make the first and last characters equal to make it a palindrome. We can do this in two ways. Either we can insert a new character before the first character, or next to the last character. 
    • For example consider “gcc”, to make first and last characters equal, we can insert a “c” first or insert a “g” last. It either becomes “cgcc” or “gccg”. since “gccg” is minimal way of making a palindrome, We just need to insert 1 character.
Let us denote the minimum number of characters to insert as MCI. It can be defined as follows. str is a string of length n.

MCI(str) = MCI( str[1:n-2] ) if str[0] = str[n-1]
         = Min( MCI(str[0:n-2]), MCI(str[1:n-1]))+1 otherwise

A naive recursive implementation is straight forward. To implement dynamic programming solution, we create a a two dimensional table of size n*n.

table[i][j] indicates MCI of the sub-string str[i:j] the table is calculated using the following rules.

table[i][i] is always 0 because a single character is a palindrome.

table[i][j] = table[i+1][j-1] if str[i] = str[j]
            = Min(table[i+1][j], table[i,j-1])+1 otherwise

We construct this table in bottom up manner i.e solve the smaller problems first and use their result to solve bigger problems. Finally table[0][n-1] contains the required value.

Below is the dynamic programming implementation in C++.

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki.
Given a set of strings, how do we find the longest common sub-sequence(LCS) among them?

For example, LCS{“ATDACG”,”CTDACGA”} is  “TAG”.

In this post, we will look at the algorithm to find the LCS of two strings. To understand the solution, let us walk through a simple example.

Let us consider the strings “ACDG”, “CAG”. We can recursively define the LCS of two strings str1, str2 of lengths n,m as follows.
LCS(str1, str2) = 
    LCS(str1[0:n-2], str2[0:m-2])+str1[n-1] if str1[n-1] = str2[m-1]
    Max(LCS(str1,str2[0:m-2], LCS(str1[0:n-2],str2)) otherwise
Using the above definition
LCS(“ACDG”,”CAG”) = LCS(“ACD”, “CA”) + “G”

This means that since the last character is same, in the sub-problem we can delete it from both the strings.
Further calculations go as follows

LCS(“ACD”, “CA”) = Max( LCS(“AC”, “CA”), LCS(“ACD”,”C”) )
LCS(“ACD”, “C”) = Max( LCS(“AC”, “C”), LCS(“ACD”,””) )

and so on… 

we can see that LCS(“ACD”,”CA”) is “C”; so “CG” is the final output.

If we implement this naive recursion, we repeat the calculation for many sub problems. For efficient implementation we use a 2 dimensional array of size (n+1)*(m+1).The table is calculated using the rules given below which directly follow from the recursive definition given above.

table[i][j]= 0 if either of the string is empty
           = 1 + table[i-1][j-1] if their last characters are equal
           = max(table[i-1][j], table[i][j-1]) otherwise

Here is an example table.

  ∅ B A C B A D
∅ 0 0 0 0 0 0 0
A  0 1 1 1 1 1 1
B  0 1 1 1 2 2 2
A  0 1 2 2 2 3 3
Z  0 1 2 2 2 3 3
D  0 1 2 2 2 3 4
C  0 1 2 3 3 3 4

Here are the python implementations of both approaches. 

   

Maximum sum of a subsequence with no contiguous elements

Given an array of positive and negative numbers, find the maximum sum of any sub sequence such that no two elements are contiguous.

For example consider the array {3,-2, 1, 7}, maximum sum is 10 for {3,7}
For {3,-2, 1, 0, -4, 2} it is 6 for {3,1,2}

This problem can be efficiently solved in O(n) time using dynamic programming technique.

The approach here is simple. We take an auxiliary array with the same size as input. 

The entries in this array are calculated as follows.

Aux[i] = Aux[i] if i = 0
       = Max( Aux[0], Aux[1] ) if i = 1
       = Max( Aux[i-2]+arr[i], Aux[i-1] ) otherwise

Here is the C++ implementation of the above approach. It takes O(n) time and O(n) space.



Finding the depth of n-ary tree given parent id representation

Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it.
 

The depth of a tree is defined as the maximum length of the path from root to any leaf node.

For example the following tree has a depth of 2 (for the path 0-2-4)

It is represented in parent id array as follows
index:    0  1  2  3  4
parent:  -1  0  0  0  2

This can be solved by first finding the depth of each node and returning the maximum among them. We can find the depth of each node by traversing the parent ids until we reach the root node. But this method takes O(n2) time if we naively calculate the depth of each node.

For example we calculate the depth of node 0 every time when we calculate the depths of it’s descendants (1,2,3,4).

We need to use a simple memorization (Dynamic Programming) to store the depths of nodes already calculated.

For example if we already have the depth of 2, then the depth(4) is depth(2)+1.

This method runs in O(n) time because each node is visited exactly once. space complexity is O(n).

The following is a C++ implementation of the above DP algorithm.

Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?
Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations
{1,1,4}
{1,1,1,3}
{3,3}
The minimum number of coins to make change for 6 is ‘2‘.
This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it’s sub-problems.
Let the amount be T and the given denominations are {d1,d2,…dn}. Create an array of size (T+1) denoted by MC[].
MC[K] denotes the minimum number coins required for amount K. It can be defined as follows

Min{ MC[K-d1], MC[K-d2],…MC[K-dn] } + 1 
This means that we can find the solution of a problem from it’s sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution. 

Following is the C++ implementation of the above algorithm.

Finding the edit distance between two strings

Given two strings as input, write a program to find the edit distance between them. 
The edit distance is defined as the minimum number of modifications to do on one string to transform it into the other string. A modification can be inserting a character, deleting a character, or replacing an existing character.
For example, consider the two strings “saturday” and “sunday”. The edit distance is 3. There is no way, we can change one string to the other in less than 3 modifications.
The 3 modifications that can be done on “saturday” are
remove ‘a’ –> sturday
remove ‘t’ –> surday
replace ‘r’ with ‘n’ –> sunday

The following is the algorithm based on dynamic programming.

Let us assume string1 is of length N and string2 is of length M. We create a table of size (N+1) X (M+1).

The entry table[i][j] gives the edit distance between prefix of string1 ending with ith character and prefix of string2 ending with jth character.

0 <= i <= N and 0 <= j <= M

We fill this table in a bottom-up manner. This is essentially solving the problem by combining the results of it’s sub-problems. (Dynamic programming). The entries are filled using the following formula

table[0][i] = i
table[i][0] = i

Explanation:
Assume that 0th character is empty, the edit distance between an empty string and a string of length ‘i’ is always ‘i’ because by deleting all the ‘i’ characters, it becomes an empty string.

table[i][j] = table[i-1][j-1] if string1[i] = string2[j]

Explanation:
If string1[i] and string2[j] are equal, we don’t need any modifications. Hence it is as same as table[i-1][j-1]

table[i][j] = Min(table[i-1][j],table[i][j-1],table[i-1][j-1]) + 1

Explanation:
If string1[i] and string2[j] are not equal, we have three choices.

  • Modify the differing character string1[i] to match string2[j]. This requires a cost of table[i-1][j-1] + 1
  • Delete string1[i] and try to match the remaining with string2. This requires a cost of table[i-1][j] + 1
  • Insert string1[i] into string2. This requires  a cost of table[i][j-1] + 1.

Finally table[N][M] contains the required answer.

The time and space complexity for this algorithm is O(n * m).

Following is the C++ implementation of the above algorithm.

Subset sum problem

Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value.

For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t have any subset with sum 100.

A simple recursive solution can be given as follows. We pass the array, the starting index, and target sum to the function. 
At each index we have two choices:
  • Include the current element and search for {sum – current_num} in the remaining set of elements.
  • Exclude the current element and search for sum in the remaining set of elements.
public static boolean hasSum(int [] array, int start, int sum)
{
if( sum == 0 ) //found the sum?
return true;

if( start > array.length-1 )//reached end of the array?
return false;

return hasSum(array, start+1, sum) || hasSum(array, start+1, sum-array[start]);

}

But this algorithm has an exponential time complexity which is not efficient. 
Let us look at more efficient approach based on Dynamic programming.
We take a boolean matrix of size (sum+1) x (N+1) where sum is the target sum and N is the size of the given set.
matrix[i][j] = true; indicates that there is a subset of array[0..j-1] which contains the sum i.
We initialize the following entries as base values.
  • matrix[0][j] = true; where 1 <= j <= N since in any set there will be empty subset with sum 0;
  • matrix[i][0] = false; where 1 <= i <= sum since we can’t find a sum > 0 in an empty array.
We calculate the remaining entries as follows.
matrix[i][j] = matrix[i][j-1];
If there exists a subset of array[0..j-2] with the sum i; then there should be a subset of array[0..j-1]also with the sum i.

If i >= array[j-1]; we check to see if matrix[i – array[j-1]][j-1] is true. This means check if there is any subset of array[0..j-2] with sum i-array[j-1].
If there is, then we assign true to this entry.

Finally we return the value at matrix[sum][N] which indicates true if there is a subset of array[0..N-1] with the given sum. Otherwise false.

Here is the Java code which implements this.


Maximum sum sub-array

Given an array of positive and negative values. We have to find the maximum sum a sub-array can have.

For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}.

To solve this problem, we take two variables to keep track of running sum and maximum sum. While iterating through the array, we keep adding the elements to the running sum. If the running sum exceeds the maximum sum, we update the maximum sum to reflect the latest maximum. If it becomes negative we reset it to zero. At the end of the iteration maximum sum variable contains the required value.

If all the elements are negative, then this program gives an output of 0 (basically the sum of zero-length sub-array). This program runs in O(n) time and O(1) space.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/25/13
* Time: 10:45 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array = {-1, 4, -2, 3, 0, -5, 1, 2};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array));
int[] array1 = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array1));
}
public static int getMaxSum(int[] array)
{
int maxSum = 0;// to keep track of maximum sum
int curSum = 0;// running sum
int i;
for( i = 0; i < array.length; i++ )
{
curSum += array[i];

if( curSum < 0 ) //reset if sum becomes negative
{
curSum = 0;
}

if( maxSum < curSum ) // update maxSum
maxSum = curSum;
}
return maxSum;
}
}