Basic DP problems categorized based on common Patterns mentioned in Aditya Verma's DP Youtube playlist

DynamicProgramming.java

// DP Youtube Playlist - https://www.youtube.com/playlist?list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go

package dp;

import java.util.Arrays;

@SuppressWarnings("ALL")
public class DynamicProgramming {

    /* Knapsack Pattern */
    private static int knapsack(int[] wt, int[] val, int W) {
        int n = wt.length;
        int[][] t = new int[n+1][W+1];

        for (int i = 1; i <= n; i++) {
            for(int j = 1; j <= W; j++) {
                if (wt[i-1] <= j) {
                    t[i][j] = Math.max(val[i-1] + t[i-1][j-wt[i-1]], t[i-1][j]);
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        return t[n][W];
    }

    private static boolean subsetSum(int[] arr, int sum) {
        int n = arr.length;

        boolean[][] t = new boolean[n+1][sum+1];

        for (int i = 0; i <= n; i++) t[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i-1] <= j) {
                    t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j];
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        return t[n][sum];
    }

    private static boolean equalSumPartition(int[] arr) {
        int n = arr.length;
        int sum = Arrays.stream(arr).sum();

        if (sum % 2 != 0) {
            return false;
        } else {
            return subsetSum(arr, sum/2);
        }
    }

    private static int countSubsetSum(int[] arr, int sum) {
        int n = arr.length;

        int[][] t = new int[n+1][sum+1];
        for (int i = 0; i <= n; i++) t[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i-1] <= j) {
                    t[i][j] = t[i-1][j-arr[i-1]] + t[i-1][j];
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        return t[n][sum];
    }

    private static int minSubsetSumDiff(int[] arr) {
        int n = arr.length;
        int sum = Arrays.stream(arr).sum();

        boolean[][] t = new boolean[n+1][sum+1];

        for (int i = 0; i <= n; i++) t[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i-1] <= j) {
                    t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j];
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= sum / 2; i++) {
            if(t[n][i]) {
                res = Math.min(res, sum - 2 * i);
            }
        }
        return res;
    }

    private static int countSubsetDiff(int[] arr, int diff) {
        int n = arr.length;
        int sum = Arrays.stream(arr).sum();

        int subsetSum = (diff + sum) / 2;
        return countSubsetSum(arr, subsetSum);
    }

    private static int targetSum(int[] arr, int sum) {
        return countSubsetDiff(arr, sum);
    }

    private static int unboundedKnapsack(int[] wt, int[] val, int W) {
        int n = wt.length;

        int[][] t = new int[n+1][W+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (wt[i-1] <= j) {
                    t[i][j] = Math.max(val[i-1] + t[i][j-wt[i-1]], t[i-1][j]);
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        return t[n][W];
    }

    private static int rodCutting(int[] lenghts, int[] price, int size) {
        return unboundedKnapsack(lenghts, price, size);
    }

    private static int coinChangeMaxWays(int[] coins, int sum) {
        int n = coins.length;

        int[][] t = new int[n+1][sum+1];

        for (int i = 0; i <= n; i++) {
            t[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (coins[i - 1] <= j) {
                    t[i][j] = t[i][j-coins[i - 1]] + t[i - 1][j];
                } else {
                    t[i][j] = t[i - 1][j];
                }
            }
        }

        return t[n][sum];
    }

    private static int coinChangeMinCoins(int[] coins, int sum) {
        int n = coins.length;

        int[][] t = new int[n+1][sum+1];

        t[0][0] = 1;

        for (int i = 1; i <= sum; i++) {
            t[0][i] = Integer.MAX_VALUE - 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (coins[i-1] <= j) {
                    t[i][j] = Math.min(1+t[i][j - coins[i-1]], t[i-1][j]);
                } else {
                    t[i][j] = t[i-1][j];
                }
            }
        }

        return t[n][sum] == Integer.MAX_VALUE - 1 ? -1 : t[n][sum];
    }

    /* Longest Common Subsequence Pattern */
    private static int longestCommonSubsequence(String x, String y, int n, int m) {
        int[][] t = new int[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (x.charAt(i-1) == y.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                } else {
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
                }
            }
        }

        return t[n][m];
    }

    private static int longestCommonSubstring(String x, String y, int n, int m) {
        int[][] t = new int[n+1][m+1];
        int res = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (x.charAt(i-1) == y.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                    res = Math.max(res, t[i][j]);
                }
            }
        }

        return res;
    }

    private static String printLongestCommonSubsequence(String x, String y, int n, int m) {
        int[][] t = new int[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (x.charAt(i-1) == y.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                } else {
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = n, j = m; i > 0 && j > 0;) {
            if (x.charAt(i-1) == y.charAt(j-1)) {
                sb.insert(0, x.charAt(i-1));
                i--;
                j--;
            } else {
                if (t[i][j-1] < t[i-1][j]) {
                    i--;
                } else {
                    j--;
                }
            }
        }

        return sb.toString();
    }

    private static int shortestCommonSupersequence(String x, String y, int n, int m) {
        return n + m - longestCommonSubsequence(x, y, n, m);
    }

    private static String countInsertionDeletionRequierdForConverting(String x, String y, int n, int m) {
        int lcs = longestCommonSubsequence(x, y, n, m);
        int deletions = n - lcs;
        int insertions = m - lcs;
        return String.format("%d %d", deletions, insertions);
    }

    private static int longestPalindromicSubsequence(String x, int n) {
        return longestCommonSubsequence(x, new StringBuilder(x).reverse().toString(), n, n);
    }

    private static String printLongestPalindromicSubsequence(String x, int n) {
        return printLongestCommonSubsequence(x, new StringBuilder(x).reverse().toString(), n, n);
    }

    private static int countDeletionRequiredForPalindrome(String x, int n) {
        return n - longestPalindromicSubsequence(x, n);
    }

    private static String printShortestCommonSupersequence(String x, String y, int n, int m) {
        int[][] t = new int[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (x.charAt(i-1) == y.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                } else {
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (x.charAt(i-1) == y.charAt(j-1)) {
                sb.insert(0, x.charAt(i-1));
                i--;
                j--;
            } else {
                if (t[i][j-1] > t[i-1][j]) {
                    sb.insert(0, y.charAt(j-1));
                    j--;
                } else {
                    sb.insert(0, x.charAt(i-1));
                    i--;
                }
            }
        }
        while (i > 0) {
            sb.insert(0, x.charAt(i-1));
            i--;
        }
        while (j > 0) {
            sb.insert(0, y.charAt(j-1));
            j--;
        }
        return sb.toString();
    }

    private static int longestRepeatingSubsequence(String x, int n) {
        int[][] t = new int[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && x.charAt(i-1) == x.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                } else {
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
                }
            }
        }

        return t[n][n];
    }

    private static String printLongestRepeatingSubsequence(String x, int n) {
        int[][] t = new int[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && x.charAt(i-1) == x.charAt(j-1)) {
                    t[i][j] = 1 + t[i-1][j-1];
                } else {
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = n, j = n; i > 0 && j > 0;) {
            if (i != j && x.charAt(i-1) == x.charAt(j-1)) {
                sb.insert(0, x.charAt(i-1));
                i--;
                j--;
            } else {
                if (t[i][j-1] > t[i-1][j]) {
                    j--;
                } else {
                    i--;
                }
            }
        }

        return sb.toString();
    }

    private static boolean sequencePatternMatching(String x, String y, int n, int m) {
        return longestCommonSubsequence(x, y, n, m) == Math.min(n, m);
    }

    private static int countInsertionRequiredForPalindrome(String x, int n) {
        return countDeletionRequiredForPalindrome(x, n);
    }

    public static void main(String[] args) {

//        System.out.println(countInsertionRequiredForPalindrome("aebcbda", 7));
//        System.out.println(sequencePatternMatching("akxy", "adxkcpy", 4 ,7));
//        System.out.println(printLongestRepeatingSubsequence("aabebcdd", 8));
//        System.out.println(longestRepeatingSubsequence("aabebcdd", 8));
//        System.out.println(printShortestCommonSupersequence("acbcf","abcdaf", 5, 6));
//        System.out.println(countDeletionRequiredForPalindrome("agbcba", 6));
//        System.out.println(printLongestPalindromicSubsequence("agbcba", 6));
//        System.out.println(longestPalindromicSubsequence("agbcba", 6));
//        System.out.println(countInsertionDeletionRequierdForConverting("heap", "pea", 4, 3));
//        System.out.println(printLongestCommonSubsequence("abcdgh", "abedkhr", 6, 7));
//        System.out.println(longestCommonSubstring("abcde", "ababcde", 5, 7));
//        System.out.println(longestCommonSubsequence("abcdgh", "abedkhr", 6, 7));
//        System.out.println(coinChangeMinCoins(new int[] {3, 4}, 10));
//        System.out.println(coinChangeMaxWays(new int[] {1, 2 ,3}, 5));
//        System.out.println(rodCutting(new int[] {1, 2, 3, 4, 5, 6, 7, 8}, new int[] {1, 5, 8, 9, 10, 17, 17, 20}, 8));
//        System.out.println(unboundedKnapsack(new int[] {1, 3, 4, 5}, new int[] {1, 4, 5, 7}, 7));
//        System.out.println(targetSum(new int[] {1, 1, 2, 3}, 1));
//        System.out.println(targetSum(new int[] {1, 1, 2, 3}, 1));
//        System.out.println(countSubsetDiff(new int[] {1, 1, 2, 3}, 1));
//        System.out.println(minSubsetSumDiff(new int[] {1, 6, 11, 5}));
//        System.out.println(countSubsetSum(new int[] {2, 3, 5, 6, 8, 10}, 10));
//        System.out.println(equalSumPartition(new int[] {1, 2, 5, 5, 9}));
//        System.out.println(subsetSum(new int[] {1, 3, 8, 5}, 11));
//        System.out.println(knapsack(new int[] {1, 3, 4, 5}, new int[] {1, 4, 5, 7}, 7));
    }
}