Top 10 Problems in Dynamic Programming (DP)

In this article, we will see the top 10 to understand dynamic programming better and get a taste of how it works. We will see these ten problems with their brute force solution and compare them with their optimized solution. Under this, we will discuss how optimization will improve the time complexity of the solution and produce the same results. We will also see the two methods for optimizing a problem: memoization and tabulation. This will give the reader a glimpse of how dynamic programming works and why it is required.

Top 10 Dynamic Programming Problems

0-1 Knapsack

In this problem, we must utilize the given weights and corresponding values and fit them into a given total upper bound of a bag to maximize the total value. One condition needs to be followed: each element can only be used once. That is, either take this element or leave it. No repetition is allowed.

Approach -1: Brute Force

We have two options:

1. To take an element and include its weight
2. To not take an element and exclude its weight

Further, we have two cases.

1. If the sum of the weight of the current element and the computed weight is greater than the required weight. In this case, we can not include the element as it will surpass the required upper bound.
2. If the sum of the weight of the current element and the computed weight is less than the required weight. In this, we take a maximum of two cases,
   1. Excluding the element and sending the next element without adding the weight of the current element.
   2. Including the element and sending the next element after adding the weight of the current element

In both cases, we send n-1 elements to the next stage.

Time Complexity: O(2ⁿ)

Space Complexity: O(1)

Approach -2: Dynamic Programming

We will compute the same result as in the previous case in the same form, excluding and including elements and their weights.

For dp[] array, we will define columns of length W and rows of length W n is the number of elements and all possible weights and store the maximum of each possible weight. The result will be dp[n-1][W-1], an indication of the maximum value when an nth element is taken and W weight is filled. 

static int knapSack(int W, int wt[], int val[], int n) {
    int[][] dp = new int[W+1][n+1];
    for(int[] row: dp) Arrays.fill(row, -1);
    return knapSack(W, wt, val, n, dp);
} 

static int knapSack(int W, int wt[], int val[], int n, int[][] dp){
    if(W==0 || n==0) return 0;
    if(dp[W][n]!=-1) return dp[W][n];
    return dp[W][n] = Math.max(knapSack(W, wt, val, n-1, dp), W-wt[n-1]>=0 ? knapSack(W-wt[n-1], wt, val, n-1, dp)+val[n-1]: 0);
} 
Code language: Java (java)

Time Complexity: O(N*W)

Space Complexity: O(N*W)

Unbounded Knapsack

In this problem, we need to utilize the given weights along with corresponding values and fit them into a given total upper bound to maximize the total value in the bag. We can add any element any number of times; repetition is allowed. 

Approach-1: Brute Force 

We have two options:

1. To take an element and include its weight
2. To not take an element and exclude its weight

Further, we have two cases.

1. If the sum of the weight of the current element and the computed weight is greater than the required weight. In this case, we can not include the element as it will surpass the required upper bound.
2. If the sum of the weight of the current element and the computed weight is less than the required weight. In this, we take a maximum of two cases,
3. Excluding the element and sending the next element without adding the weight of the current element and sending n-1 elements.
4. Including the element and sending the next element after adding the weight of the current element and sending n elements as repetition is allowed.

Time Complexity: O(2ⁿ)

Space Complexity: O(1)

Approach -2: Dynamic Programming

We will compute the same result as in the previous case in the same form, excluding and including elements and their weights.

For dp[] array, we will define columns of length W and rows of length W as the number of elements and all possible weights and store the maximum of each possible weight. The result will be dp[n-1][W-1], an indication of the maximum value when an nth element is taken, and W weight is filled.

static int knapSack(int N, int W, int val[], int wt[]){
     int[] dp = new int[W+1];
        dp[0] = 0;
        for(int bagc=1;bagc<dp.length;bagc++){
            int max = 0;
            for(int w = 0; w<N;w++ ){
                if(wt[w]<=bagc){
                    max = Math.max(dp[bagc-wt[w]]+val[w],max);
                }
            }
            dp[bagc] = max;
        }
    return dp[W]; 
}
Code language: Java (java)

Time Complexity: O(N*W)

Space Complexity: O(N*W)

Target Sum Subset

In this problem, we have to determine whether the given set of arrays contains elements that sum up to a target. The result of this problem is either true or false.

Approach-1: Brute Force

We have two cases that arise in this problem,

1. Take the current element, decrease the target’s magnitude, and call for n-1 elements.
2. Exclude the current element, decrease the target magnitude, and call for n-1 elements.

Time Complexity: O(2ⁿ)

Space Complexity: O(1)

Approach-2: Dynamic Programming

While maintaining the above conditions, we can use a 2-dimensional array where rows correspond to the number of elements and columns corresponds to 0 to target values. For example, a cell in this 2D array is defined as whether the I number of elements in the given array sum up to j, where i is the ith index and j is the jth index.

static Boolean isSubsetSum(int N, int arr[], int sum){
    int[][] dp = new int[N+1][sum+1];
    for(int[] row: dp) Arrays.fill(row,-1);
    return isSubsetSum(N, arr, sum, dp);
}
    
static Boolean isSubsetSum(int N, int arr[], int sum, int[][] dp){
    if(sum==0) return true;
    if(N==0) return false;
    if(dp[N][sum]!=-1) return dp[N][sum]==0 ? false : true;
    boolean ans = isSubsetSum(N-1, arr, sum, dp) || (sum-arr[N-1]>=0?isSubsetSum(N-1, arr, sum-arr[N-1], dp) : false);
    dp[N][sum] = ans == false ? 0 : 1;
    return ans;
}
Code language: Java (java)

Time Complexity: O(N*W)

Space Complexity: O(N*W)

Rod Cutting Problem

Under this problem, we are given a rod of length, and we have specific values at each length. The task is to cut the rod into pieces to obtain maximum value. 

Approach-1: Brute Force

In this, we will use recursion to solve the problem. Under this, two cases arise,

1. If the current index is greater than the length of the rod, then we have no choice but to exclude this and make a call on n-1 elements.
2. Else, we take a maximum of the two cases:
   1. Include the price of the current index, and call on the current index and length index.
   2. Exclude the price of the current index, call on the n-1 index and keep the length the same.

Approach-2: Dynamic Programming

While maintaining the above conditions, we can use a 2-dimensional array where rows and columns correspond to the size of the rod and the size of rod+1, respectively. For example, one cell denotes the maximum price required to compute the cutting of i length of the rod up to jth elements.

public int cutRod(int price[], int n) {
    Integer[][] dp = new Integer[n+1][n+1];
    return cutRod(price, n, n, dp);
}
    
public int cutRod(int price[], int n, int i, Integer[][] dp){
    if(n==0) return 0;
    if(i==0) return 0;
    if(dp[i][n] !=null) return dp[i][n];
    return dp[i][n] = Math.max(cutRod(price, n, i-1, dp) , (n-i>=0) ? cutRod(price, n-i, i, dp)+price[i-1] : 0);
}
Code language: Java (java)

Coin Change Problem

This problem calls for finding the fewest coins from a given array of coins of different denominations that sum up to a particular target.

Approach-1: Brute Force

We have two instances that can happen while solving this problem,

1. If the current target is less than the current element’s value, then we can’t add this coin to our result.
2. Else there are two cases, out of which we take a minimum of two.
   1. Include the element, call for n elements and add 1 to the result.
   2. Exclude the element and call for n-1 elements. 

Approach-2: Dynamic Programming

We use the above conditions and use storage to avoid re-evaluation. For example, we take a 2-D array with a size equal to the number of elements N into the target value, M, dp[N][M]. One cell indicates the minimum coins required to sum up to the target.

int coinChange(int[] coins, int amount) {
    dp = new Long[coins.length+1][amount+1];
    long ans = coinChange(coins, amount, coins.length, 0);
    return ans!=Integer.MAX_VALUE ? (int)ans : -1;
}
    
Long[][] dp;
    
private long coinChange(int[] coins, int amount, int n, int count){
    if(amount==0) return 0;
    if(n==0) return Integer.MAX_VALUE;
    if(dp[n][amount]!=null) return dp[n][amount];
    return dp[n][amount] = Math.min(coinChange(coins, amount, n-1, count), (amount-coins[n-1]>=0) ? coinChange(coins, amount-coins[n-1], n, count+1)+1 : Integer.MAX_VALUE);
}
Code language: Java (java)

Time Complexity: O(N*W)

Space Complexity: O(N*W)  

Coin Change Problem – 2

This problem calls for finding the number of combinations possible from a given array of coins of different denominations that sum up to a particular target. 

Approach-1: Brute force

We have two instances that can happen while solving this problem,

1. If the current target is less than the current element’s value, then we can’t add this coin to our result.
2. Else take both cases, that is, add this coin’s denomination towards the result, send n elements, exclude current elements, and call for n-1 elements.

Time Complexity: O(2^m) m being the target

Space Complexity: O(1)

Approach-2: Dynamic Programming

The only difference in this approach is that we create a storage of a 2-D array where rows are several elements and columns are of the size of the target value. For example, one cell denotes the number of combinations possible to create the jth sum from elements up to the ith index.

public int change(int amount, int[] coins) {
    dp = new Integer[coins.length+1][amount+1];
    return change(amount, coins, coins.length);
}

Integer[][] dp;
    
private int change(int amount, int[] count, int n){
    if(amount == 0) return 1;
    if(n==0) return 0;
    if(dp[n][amount]!=null) return dp[n][amount];
    return dp[n][amount] = change(amount, count, n-1) + ((amount-count[n-1]>=0) ? change(amount-count[n-1], count, n) : 0 );
}
Code language: Java (java)

Time Complexity: O(M*N), M being the target and N being the size of the array

Space Complexity: O(M*N)

Longest Increasing Subsequence

The problem asks for the length of the longest subsequence put of an array sorted in ascending order.

Approach:
We take an array that stores the length of the longest subsequence until the ith index. That is, it compares the last i elements, checks if they are smaller than the current element, and takes the maximum of all the elements.

private int binarySearch(ArrayList<Integer> lis, int ele){
    int lo = 0, hi = lis.size()-1;
     
    while(lo<hi){
        int mid = lo + (hi-lo)/2;
        if(lis.get(mid)<ele){
            lo = mid+1;
        }
        else{
            hi = mid;
        }
    }
        
    return lo;
}

public int lengthOfLIS(int[] nums) {
    ArrayList<Integer> lis = new ArrayList<>();
    lis.add(nums[0]);
        
    for(int i=0; i<nums.length; i++){
        if(lis.get(lis.size()-1)<nums[i]){
            lis.add(nums[i]);
        }
        else{
            int idx = binarySearch(lis,nums[i]);
            lis.set(idx, nums[i]);
        }
    }
        
    return lis.size();
}
Code language: Java (java)

Time Complexity: O(N²)

Space Complexity: O(N)

Longest Common Subsequence

This problem takes two strings and produces the length of the subsequences common in both strings but in order. For example, abcde and bucid have the LCS of bcd length 3.

Approach:

We take a 2-D array of size corresponding to one more than the length of both of the strings. Then we iterate on each character of one string for every character of another. This gives us 3 cases

1. We are at an index if any indexes are 0 before starting the string. Hence we store the length as 0.
2. If the characters at both indices i-1 and j-1 are equal, then we store dp[i-][j-1]+1 at dp[i][j].
3. If the characters at indices i-1 and j-1 are not equal, then we take the maximum of dp[i-1][j] and dp[i][j-1].

public int longestCommonSubsequence(String text1, String text2) {
    int[][] dp = new int[text1.length()+1][text2.length()+1];
    for(int i=1; i<dp.length; i++){
        for(int j=1; j<dp[0].length; j++){
            dp[i][j] = text1.charAt(i-1) == text2.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[text1.length()][text2.length()];
}
Code language: Java (java)

Time complexity: O(text1.length*text2.length)

Space Complexity: O(text1.length*text2.length)

Longest Palindromic Subsequence

In this problem, we are given a string, from which we need to find the length of the longest subsequence, a palindrome. 

Approach:

1. We can reverse the provided string.
2. Find the Longest Common Subsequence of the current and the reversed string.

This gives us the length of the palindrome because the LCS of a string and its reverse will be calculated only if a palindrome exists.

public int longestPalindromeSubseq(String s) {
    String s2 = reverseString(s);
    int[][] dp = new int[s.length()+1][s.length()+1];
    for(int i=1; i<dp.length; i++){
        for(int j=1; j<dp.length; j++){
            if(s.charAt(i-1)==s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[s.length()][s.length()];
}
    
private String reverseString(String s){
    StringBuilder sb = new StringBuilder(s);
    int i = 0;
    int j = s.length()-1;
    while(i<j){
        sb.setCharAt(i, s.charAt(j));
        sb.setCharAt(j, s.charAt(i));
        i++;
        j--;
    }
    return sb.toString();
}
Code language: Java (java)

Time Complexity: O(N²)

Space Complexity: O(N²)

Matrix Chain Multiplication

In this problem, we are given an array, which denotes the columns and rows of a matrix. Example: 20 30 40 50 means there’s a matrix A with size 20×30, matrix B with size 30×40, and so on. We need to compute the minimum operations required to multiply these matrices. 

Approach:

1. We create storage of N*N, where N is the size of the given array.
2. Iterate on the whole array, and let it be denoted by g. 
3. Now iterate on the partition from i=0, j=g until j <array.length. This partitions our array from i to the j index.
4. Further, divide this partition into i to k and from k+1 to j. This gives us the multiplication that provides the output of A[i]*A[k]*A[j], which is the computed result for a 2D matrix with dimensions A[i]*A[k] and A[k+1]*A[j+1].
5. The total possible answer is the sum of operations for the left part, dp[i][k], right part, dp[k+1][j], and the computed result A[i]*A[k]*A[j]. We take the minimum of the answers developed by these partitions done by k and store them in dp[i][j].

static int matrixMultiplication(int N, int arr[]){
    int[][] dp = new int[N-1][N-1];
    for(int g=0; g<arr.length; g++){
        for(int i=0, j=g; j<dp.length; i++, j++){
            if(g==0) continue;
            if(g==1) dp[i][j] = arr[i]*arr[j]*arr[j+1];
            else{
                int min = Integer.MAX_VALUE;
                for(int k=i; k<j; k++){
                    int lc = dp[i][k];
                    int rc = dp[k+1][j];
                    int mc = arr[i]*arr[k+1]*arr[j+1];
                    min = Math.min(lc+rc+mc, min);
                }   
                dp[i][j] = min;
            }
        }
    }
    return dp[0][arr.length-2];
}
Code language: Java (java)

Time Complexity: O(N³)

Space Complexity: O(N²)

Conclusion

You have now understood the most fundamental problems in dynamic programming there are to offer. The new questions on dynamic programming are based on either these concepts or these problems will help you build logic for the same. The author urges the readers to dry run all these problems on a piece of paper and code by themselves to get a better understanding of how and why the code is working.

Read more about learning paths at codedamn here

Happy Learning!