Massive Algorithms: List of Dynamic Programming Algorithm

List of Dynamic Programming Algorithm

Dynamic Programming is a technique that takes advantage of overlapping subproblems, optimal substructure, and trades space for time to improve the runtime complexity of algorithms.

Optimal Substructure

Overlapping Subproblems

http://www.algorithmist.com/index.php/Dynamic_Programming
There are two types of Dynamic Programming: Top-Down or Bottom-Up. The Top-Down method is often called Memoization.
Memoization
http://www.slideshare.net/kyleburton/fuzzy-string-matching
The concept is to cache the result of a function given its parameter so that the calculation will not be repeated; it is simply retrieved, or memo-ed. Most of the time a simple array is used for the cache table, but a hash table or map could also be employed.

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).
Optimal Substructure
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).
A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

Matrix Chain Multiplication

Dynamic Programming | Set 8 (Matrix Chain Multiplication) | GeeksforGeeks

Given a sequence of matrices, find the most efficient way to multiply these matrices together.


let the chain be ABCD, then there are 3 way to place first set of parenthesis: A(BCD), (AB)CD and (ABC)D. So when we place a set of parenthesis, we divide the problem into subproblems of smaller size. 

Also check http://en.wikipedia.org/wiki/Matrix_chain_multiplication

Palindrome Partitioning

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string.
O(n^3)

/ i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.

// If none of the above conditions is true, then minPalPartion(str, i, j) can be 
// calculated recursively using the following formula.
minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +
                                 minPalPartion(str, k+1, j) } 
                           where k varies from i to j-1

Egg Dropping Puzzle
Dynamic Programming | Set 11 (Egg Dropping Puzzle) | GeeksforGeeks

 k ==> Number of floors
  n ==> Number of Eggs
  eggDrop(n, k) ==> Minimum number of trails needed to find the critical
                    floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x in {1, 2, ..., k}}

0-1 Knapsack Problem Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) | GeeksforGeeks
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.
o consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

Cutting a Rod Dynamic Programming | Set 13 (Cutting a Rod) | GeeksforGeeks
Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

max_val = max(max_val, price[i] + cutRod(price, n-i-1));

Longest Palindromic Subsequence
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://massivealgorithms.blogspot.com/2014/06/leetcode-longest-palindromic-substring.html

Let p[i,j] denote whether the substring Si…Sj is palindromic. It can be observed that p[i,j] is true if and only if p[i+1,j−1] is true and Si=Sj . The base cases for this recursion are that p[i,i] is true and that p[i,i+1] is true if and only if Si=Si+1 . Starting from the base cases, the algorithm finds three- and more-letters palindromes. This gives a run time ofO(n2) and uses O(n2) space.

Largest Independent Set Problem Dynamic Programming | Set 26 (Largest Independent Set Problem) | GeeksforGeeks
Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset.

Let LISS(X) indicates size of largest independent set of a tree with root X.

     LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
                     (sum of LISS for all children of X) }

The idea is simple, there are two possibilities for every node X, either X is a member of the set or not a member. If X is a member, then the value of LISS(X) is 1 plus LISS of all grandchildren. If X is not a member, then the value is sum of LISS of all children.

Time Complexity: O(n)

Subset Sum Problem http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || 
                           isSubsetSum(arr, n-1, sum-set[n-1])

We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]

Maximum subarray problem - Max Sum - Continuous subarray
http://en.wikipedia.org/wiki/Maximum_subarray_problem

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   int i;

   for(i = 0; i < size; i++)

   {

     max_ending_here = max_ending_here + a[i];

     if(max_ending_here < 0)

         max_ending_here = 0;

     /* Do not compare for all elements. Compare only   

        when  max_ending_here > 0 */

     else if (max_so_far < max_ending_here)

         max_so_far = max_ending_here;

   }

   return max_so_far;

}

Algorithm doesn't work for all negative numbers. It simply returns 0 if all numbers are negative. For handling this we can add an extra phase before actual implementation. The phase will look if all numbers are negative, if they are it will return maximum of them (or smallest in terms of absolute value)

Longest Common Subsequence
let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).
If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Longest Increasing Subsequence (LIS)
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n

 for ( i = 1; i < n; i++ )

      for ( j = 0; j < i; j++ )

         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

Better Solution: Patient Sorting - O(nlogn)
http://rosettacode.org/wiki/Longest_increasing_subsequence#Java

Maximum Sum Increasing Subsequence Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence) | GeeksforGeeks
We need a slight change in the Dynamic Programming solution of LIS problem. All we need to change is to use sum as a criteria instead of length of increasing subsequence.

Box Stacking Problem

http://people.csail.mit.edu/bdean/6.046/dp/.
Dynamic Programming | Set 22 (Box Stacking Problem) | GeeksforGeeks

1) Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.

2) Sort the above generated 3n boxes in decreasing order of base area.

3) After sorting the boxes, the problem is same as LIS with following optimal substructure property.
MSH(i) = Maximum possible Stack Height with box i at top of stack
MSH(i) = { Max ( MSH(j) ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i).
If there is no such j then MSH(i) = height(i)

4) To get overall maximum height, we return max(MSH(i)) where 0 < i < n

Maximum Length Chain of Pairs Dynamic Programming | Set 20 (Maximum Length Chain of Pairs) | GeeksforGeeks
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.
1) Sort given pairs in increasing order of first (or smaller) element.
2) Now run a modified LIS process where we compare the second element of already finalized LIS with the first element of new LIS being constructed.

Word Wrap Problem Dynamic Programming | Set 19 (Word Wrap Problem) | GeeksforGeeks

Dynamic Programming | Set 18 (Partition problem) | GeeksforGeeks
Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.


Dynamic Programming SolutionThe problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array part[][] of size (sum/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property
part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum
             equal to i, otherwise false

     // Fill the partition table in botton up manner 

     for (i = 1; i <= sum/2; i++)  

{

       for (j = 1; j <= n; j++)  

{

         part[i][j] = part[i][j-1];

         if (i >= arr[j-1])

           part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];

}

}

Minimum # coins required to make change
http://www.algorithmist.com/index.php/Min-Coin_Change
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/money-change.html

C (N, m) = min(C (N, m - 1), C (N - S m, m) + 1)

with the base cases:

$C (N, m) = 1, N = 0$
$C (N, m) = 0, N < 0$
$C( N, m ) = 0, N \geq 1, m \leq 0$

Coin Change
If we want to make change for

N

cents, and we have infinite supply of each of $S = \{ S_1, S_2, \ldots, S_m \}$ valued coins, how many ways can we make the change?
http://www.algorithmist.com/index.php/Coin_Change
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

C (N, m) = C (N, m - 1) + C (N - S m, m)

with the base cases:

$C (N, m) = 1, N = 0$ (one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0)
$C( N, m ) = 0, N \leq 0$ (no solution -- negative sum of money)
$C( N, m ) = 0, N \geq 1, m \leq 0$ (no solution -- we have money, but no change available)

Minimum number of jumps to reach end http://algorithmsandme.blogspot.com/2014/03/arrays-minimum-jumps-to-reach-at-end.html
Minimum number of jumps to reach end | GeeksforGeeks
we build a jumps[] array from left to right such that jumps[i] indicates the minimum number of jumps needed to reach arr[i] from arr[0]. Finally, we return jumps[n-1].

Largest Sum Contiguous Subarray http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Edit Distance
Given two strings

s 1

and

s 2

, the edit distance between

s 1

and

s 2

is the minimum number of operations required to convert string

s 1

s 2

.
http://en.wikipedia.org/wiki/Edit_distance

d_{i0} = \sum_{k=1}^{i} w_\mathrm{del}(b_{k}), \quad for\; 1 \leq i \leq m

d_{0j} = \sum_{k=1}^{j} w_\mathrm{ins}(a_{k}), \quad for\; 1 \leq j \leq n

d_{ij} = \begin{cases} d_{i-1, j-1} & \quad a_{j} = b_{i}\\ \min \begin{cases} d_{i-1, j} + w_\mathrm{del}(b_{i})\\ d_{i,j-1} + w_\mathrm{ins}(a_{j}) \\ d_{i-1,j-1} + w_\mathrm{sub}(a_{j}, b_{i}) \end{cases} & \quad a_{j} \neq b_{i}\end{cases} , \quad for\; 1 \leq i \leq m, 1 \leq j \leq n.

Damerau-Levenshtein distance

Damerau-Levenshtein algorithm's work process

Maximum size square sub-matrix with all 1s Maximum size square sub-matrix with all 1s | PROGRAMMING INTERVIEWS
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.
We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.
How to calculate S[i][j]:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.

If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:

S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1

Optimal Binary Search Tree Dynamic Programming | Set 24 (Optimal Binary Search Tree) | GeeksforGeeks
Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

1) Optimal Substructure:
The optimal cost for freq[i..j] can be recursively calculated using following formula.
$optCost(i, j) = \sum\limits_{k=i}^j freq[k] + \min\limits_{r=i}^j [ optCost(i, r-1) + optCost(r+1, j) ]$

We need to calculate optCost(0, n-1) to find the result.

The idea of above formula is simple, we one by one try all nodes as root (r varies from i to j in second term). When we make rth node as root, we recursively calculate optimal cost from i to r-1 and r+1 to j.
We add sum of frequencies from i to j (see first term in the above formula), this is added because every search will go through root and one comparison will be done for every search.

Get maximum sum from coins in a line Get maximum sum from coins in a line | PROGRAMMING INTERVIEWS
There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
C(i, j) is the maximum sum possible when remaining coins are from i to j.

C(i, j)  = max { C1, C2 }   
= max { Ai + min { C(i+2, j),   C(i+1, j-1) },
        Aj + min { C(i+1, j-1), C(i,   j-2) } }

Max possible sum of non-consecutive elements | PROGRAMMING INTERVIEWS
There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.

If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }
S(-1) = 0;
if i=0, S(i) = T(0);

Unique Paths in 2D grid | PROGRAMMING INTERVIEWS
There is an m x n grid. One can only move either down or right at any point in time. One is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
Paths[i][j] = paths[i][j-1] + paths[i-1][j]

Avid TV watcher | PROGRAMMING INTERVIEWS
There is a TV avid person, who wants to spend his maximum time on TV. There are N channels that telecast programs of different length at different timings. WAP to find the program and channel number so that the person can spend his max time on TV.
Lets calculate that if I includes program x in my schedule then how can I spent most of my time on tv till the end of program x. So when I calculate the same for the last program among all the channels, I will be easily able to tell that what will be maximum time, I can spend on tv

List of Dynamic Programming Algorithm

Labels

Popular Posts