Dynamic programming Flashcards
Longest Increasing subsequence
ony one aux array needed
checks on the basis of if arr[i] > arr[j] and table[j] + 1 > table[i]
int []lis = new int[n];
int i,j,max = 0;
/* Initialize LIS values for all indexes */
for ( i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
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;
/* Pick maximum of all LIS values */
for ( i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
return max;
Longest Common Subsequence
Create a table and check if the two chars at this match
if match then value = 1 + table[i-1,j-1]
else
Math.Max(table[i-1][j], table[i,j - 1]
int [,]L = new int[m+1,n+1];
/* Following steps build L[m+1][n+1]
in bottom up fashion. Note
that L[i][j] contains length of
LCS of X[0..i-1] and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i, j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i, j] = L[i - 1, j - 1] + 1;
else
L[i, j] = max(L[i - 1, j], L[i, j - 1]);
}
}
return L[m, n];
0 -1 Knapsack
For each item can be or not included in the optimal subset
this means we check if the weight by adding the element is less than the given weight
int i, w;
int [,]K = new int[n+1,W+1];
// Build table K[][] in bottom
// up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i,w] = 0;
else if (wt[i-1] <= w)
K[i,w] = Math.Max(val[i-1]
\+ K[i-1,w-wt[i-1]],
K[i-1,w]);
else
K[i,w] = K[i-1,w];
}
}
return K[n,W];
Maximum sum increasing subsequence
maintain a single table array like in LIS
this should be a copy of th given array
check arr[i] > arr[j] and table[i] + array[j]
update if it is
int i, j, max = 0;
int []msis = new int[n];
/* Initialize msis values
for all indexes */
for ( i = 0; i < n; i++ )
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all
msis values */
for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];
return max;
Minimum number of jumps to reach end
int []jumps = new int[n];
// if first element is 0,
if (n == 0 || arr[0] == 0)
// end cannot be reached
return int.MaxValue;
jumps[0] = 0;
// Find the minimum number of
// jumps to reach arr[i]
// from arr[0], and assign
// this value to jumps[i]
for (int i = 1; i < n; i++)
{
jumps[i] = int.MaxValue;
for (int j = 0; j < i; j++)
{
if (i <= j + arr[j] && jumps[j] != int.MaxValue )
{
jumps[i] = Math.Min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
Edit Distance
int editDistDP(string str1, string str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m+1][n+1];
// Fill d[][] in bottom up manner
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
// If first string is empty, only option is to
// insert all characters of second string
if (i==0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j==0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1];
// If the last character is different, consider all
// possibilities and find the minimum
else
dp[i][j] = 1 + min(dp[i][j-1], // Insert
dp[i-1][j], // Remove
dp[i-1][j-1]); // Replace
}
}
return dp[m][n]; }
Minimum Operations from 0 to n
if given m and result n
if m > n
result = m -n
else if n is odd add one to it
else m = m* n
Max length chain
we create a table aray all with 1
we check from 1 to n
if arr[j].Item2 < arr[i].Item1 table[i] = table[i] + 1
Minimum number of Coins
we create table with[n +1, Target + 1]
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=V; i++)
table[i] = INT_MAX;
// Compute minimum coins required for all
// values from 1 to V
for (int i=1; i<=V; i++)
{
// Go through all coins smaller than i
for (int j=0; j
Longest Common Substring
int LCSuff[m+1][n+1];
int result = 0; // To store length of the
// longest common substring
/* Following steps build LCSuff[m+1][n+1] in
bottom up fashion. */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
// The first row and first column
// entries have no logical meaning,
// they are used only for simplicity
// of program
if (i == 0 || j == 0)
LCSuff[i][j] = 0;
else if (X[i-1] == Y[j-1])
{
LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
result = max(result, LCSuff[i][j]);
}
else LCSuff[i][j] = 0;
}
}
return result;
Time Complexity: O(m*n)
