10 most common problems Dynamic Programming?

10 most common problems Dynamic Programming?

1. Longest Common Subsequence
2. Longest Increasing Subsequence
3. Edit Distance
4. Minimum Partition
5. Ways to Cover a Distance
6. Longest Path In Matrix
7. Subset Sum Problem
8. Optimal Strategy for a Game
9. 0-1 Knapsack Problem
10. Boolean Parenthesization Problem

Longest Common Subsequence?
1) Optimal Substructure:
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And 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])

2. Longest Increasing Subsequence?
There is a recursive way, dynamic programming with brute force , and a nlogn version
brute force dynamic programming version O(n^2)


def lis(arr):
n = len(arr)

# Declare the list (array) for LIS and initialize LIS
# values for all indexes
lis = [1]*n

# Compute optimized LIS values in bottom up manner
for i in range (1 , n):
for j in range(0 , i):
if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
lis[i] = lis[j]+1

# Initialize maximum to 0 to get the maximum of all
# LIS
maximum = 0

# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum , lis[i])

return maximum
# end of lis function

3. Edit Distance?
def editDistDP(str1, str2, m, n):
# Create a table to store results of subproblems
dp = [[0 for x in range(n+1)] for x in range(m+1)]

# Fill d[][] in bottom up manner
for i in range(m+1):
for j in range(n+1):

# If first string is empty, only option is to
# isnert 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
elif j == 0:
dp[i][j] = i # Min. operations = i

# If last characters are same, ignore last char
# and recur for remaining string
elif str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]

# If last character are different, consider all
# possibilities and find 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]

4. Minimum Partition
The task is to divide the set into two parts.
We will consider the following factors for dividing it.
Let
dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum
equal to j
0 otherwise}

i ranges from {1..n}
j ranges from {0..(sum of all elements)}

So
dp[n+1][sum+1] will be 1 if
1) The sum j is achieved including i'th item
2) The sum j is achieved excluding i'th item.

Let sum of all the elements be S.

To find Minimum sum difference, w have to find j such
that Min{sum - j*2 : dp[n][j] == 1 }
where j varies from 0 to sum/2

The idea is, sum of S1 is j and it should be closest
to sum/2, i.e., 2*j should be closest to sum.

5. Ways to Cover a Distance
class GFG
{
// Function returns count of ways to cover 'dist'
static int printCountDP(int dist)
{
int[] count = new int[dist+1];

// Initialize base values. There is one way to
// cover 0 and 1 distances and two ways to
// cover 2 distance
count[0] = 1;
count[1] = 1;
count[2] = 2;

// Fill the count array in bottom up manner
for (int i=3; i<=dist; i++)
count[i] = count[i-1] + count[i-2] + count[i-3];

return count[dist];
}

// driver program
public static void main (String[] args)
{
int dist = 4;
System.out.println(printCountDP(dist));
}
}

6. Longest Path In Matrix
The idea is simple, we calculate longest path beginning with every cell. Once we have computed longest for all cells, we return maximum of all longest paths. One important observation in this approach is many overlapping subproblems. Therefore this problem can be optimally solved using Dynamic Programming.

Below is Dynamic Programming based implementation that uses a lookup table dp[][] to check if a problem is already solved or not.

7. Subset Sum Problem
We can solve the problem in Pseudo-polynomial time using Dynamic programming. 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]

8. Optimal Strategy for a Game
{
// Create a table to store solutions of subproblems
int table[][] = new int[n][n];
int gap, i, j, x, y, z;

// Fill table using above recursive formula.
// Note that the tableis filled in diagonal
// fashion (similar to http://goo.gl/PQqoS),
// from diagonal elements to table[0][n-1]
// which is the result.
for (gap = 0; gap < n; ++gap)
{
for (i = 0, j = gap; j < n; ++i, ++j)
{
// Here x is value of F(i+2, j),
// y is F(i+1, j-1) and z is
// F(i, j-2) in above recursive formula
x = ((i + 2) <= j) ? table[i + 2][j] : 0;
y = ((i + 1) <= (j - 1)) ? table[i +1 ][j - 1] : 0;
z = (i <= (j - 2)) ? table[i][j - 2]: 0;

table[i][j] = Math.max(arr[i] +
Math.min(x, y), arr[j] +
Math.min(y, z));
}
}

return table[0][n - 1];
}

9. 0-1 Knapsack Problem
# A Dynamic Programming based Python Program for 0-1 Knapsack problem
# Returns the maximum value that can be put in a knapsack of capacity W
def knapSack(W, wt, val, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]

# Build table K[][] in bottom up manner
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = 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]

10. Boolean Parenthesization Problem
If we draw recursion tree of above recursive solution, we can observe that it many overlapping subproblems. Like other dynamic programming problems, it can be solved by filling a table in bottom up manner. Following is C++ implementation of dynamic programming solution.