Dynamic Programming

Factorial using DP

Memoization

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int[] memo;

    static int fib(int n) {
        if (memo[n] == -1) {
            int res;

            if (n == 0 || n == 1)
                return n;

            else {
                res = fib(n - 1) + fib(n - 2);

            }

            memo[n] = res;

        }

        return memo[n];
    }

    public static void main(String[] args) {

        int n = 5;

        memo = new int[n + 1];

        Arrays.fill(memo, -1);

        out.println(fib(n));

    }
}

Tabulation

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int fib(int n) {
        int f[] = new int[n + 1];

        f[0] = 0;
        f[1] = 1;

        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];

    }

    public static void main(String[] args) {

        int n = 5;

        out.println(fib(n));

    }
}

Longest Common Subsequence (Part 1)

Memoization

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int[][] memo;

    static int lcs(String s1, String s2, int n, int m) {
        if (memo[n][m] != -1)
            return memo[n][m];

        if (n == 0 || m == 0)
            memo[n][m] = 0;

        else {
            if (s1.charAt(n - 1) == s2.charAt(m - 1))
                memo[n][m] = 1 + lcs(s1, s2, n - 1, m - 1);
            else
                memo[n][m] = Math.max(lcs(s1, s2, n - 1, m), lcs(s1, s2, n, m - 1));
        }

        return memo[n][m];

    }

    public static void main(String[] args) {

        String s1 = "AXYZ", s2 = "BAZ";

        int n = 4, m = 3;

        memo = new int[n + 1][m + 1];

        for (int[] i : memo) {
            Arrays.fill(i, -1);
        }

        System.out.println(lcs(s1, s2, n, m));

    }
}

Tabulation

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();

        int dp[][] = new int[m + 1][n + 1];

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

        return dp[m][n];

    }

    public static void main(String[] args) {

        String s1 = "AXYZ", s2 = "BAZ";

        System.out.println(lcs(s1, s2));

    }
}

Variation of LCS

• Diff Utility

• Min. insert or delete to convert s1 to s2

• Short common sequence

• Longest Palindrome Sub sequence

• Longest Repeating Sub sequence

• Printing LCS

Coin Change Count Combinations

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int getCount(int coins[], int n, int sum) {
        int dp[][] = new int[sum + 1][n + 1];

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

        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1];

                if (coins[j - 1] <= i)
                    dp[i][j] += dp[i - coins[j - 1]][j];
            }
        }

        return dp[sum][n];

    }

    public static void main(String[] args) {

        int coins[] = { 1, 2, 3 }, sum = 4, n = 3;

        System.out.println(getCount(coins, n, sum));

    }
}

Edit Distance Problem

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int eD(String s1, String s2, int m, int n) {
        if (m == 0)
            return n;
        if (n == 0)
            return m;

        if (s1.charAt(m - 1) == s2.charAt(n - 1))
            return eD(s1, s2, m - 1, n - 1);
        else {
            return 1 + Math.min(eD(s1, s2, m, n - 1), Math.min(eD(s1, s2, m - 1, n), eD(s1, s2, m - 1, n - 1)));
        }

    }

    public static void main(String[] args) {

        String s1 = "CAT", s2 = "CUT";
        int n = 3, m = 3;

        System.out.println(eD(s1, s2, m, n));

    }
}

Edit Distance Problem DP

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int eD(String s1, String s2, int m, int n) {
        int dp[][] = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));

                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {

        String s1 = "CAT", s2 = "CUT";
        int n = 3, m = 3;

        System.out.println(eD(s1, s2, m, n));

    }
}

Longest Increasing Subsequence Problem

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int LIS(int arr[], int n) {
        int lis[] = new int[n];

        lis[0] = 1;

        for (int i = 1; i < n; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++)
                if (arr[i] > arr[j])
                    lis[i] = Math.max(lis[i], lis[j] + 1);
        }

        int res = lis[0];

        for (int i = 0; i < n; i++) {
            res = Math.max(lis[i], res);
        }

        return res;

    }

    public static void main(String[] args) {
        int arr[] = { 3, 4, 2, 8, 10, 5, 1 };
        int n = 7;

        System.out.println(LIS(arr, n));

    }
}

Longest Increasing Subsequence O( nlog(n) )

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int ceilIdx(int tail[], int l, int r, int key) {
        while (r > l) {
            int m = l + (r - l) / 2;
            if (tail[m] >= key)
                r = m;
            else
                l = m + 1;
        }

        return r;
    }

    static int LIS(int arr[], int n) {

        int[] tail = new int[n];
        int len = 1;

        tail[0] = arr[0];

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

            if (arr[i] > tail[len - 1]) {
                tail[len] = arr[i];
                len++;
            } else {
                int c = ceilIdx(tail, 0, len - 1, arr[i]);

                tail[c] = arr[i];
            }
        }

        return len;
    }

    public static void main(String[] args) {
        int arr[] = { 3, 10, 20, 4, 6, 7 };
        int n = 6;

        System.out.println(LIS(arr, n));

    }
}

Variation of LIS

• Minimum deletions to make array sorted

• Maximum Sum Increasing Sub sequence

• Max Length Bitonic Solution

• Building Bridges

• The longest chain

Maximum Cuts

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int maxCuts(int n, int a, int b, int c) {

        int dp[] = new int[n + 1];

        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = -1;

            if (i - a >= 0)
                dp[i] = Math.max(dp[i], dp[i - a]);

            if (i - b >= 0)
                dp[i] = Math.max(dp[i], dp[i - b]);

            if (i - c >= 0)
                dp[i] = Math.max(dp[i], dp[i - c]);

            if (dp[i] != -1)
                dp[i]++;
        }

        return dp[n];

    }

    public static void main(String[] args) {
        int n = 5, a = 1, b = 2, c = 3;

        System.out.println(maxCuts(n, a, b, c));

    }
}

Minimum coins to make a value

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int minCoins(int arr[], int m, int value) {

        int dp[] = new int[value + 1];

        dp[0] = 0;

        for (int i = 1; i <= value; i++)
            dp[i] = Integer.MAX_VALUE;

        for (int i = 1; i <= value; i++) {

            for (int j = 0; j < m; j++)
                if (arr[j] <= i) {
                    int sub_res = dp[i - arr[j]];
                    if (sub_res != Integer.MAX_VALUE && sub_res + 1 < dp[i])
                        dp[i] = sub_res + 1;

                }

        }
        return dp[value];

    }

    public static void main(String[] args) {
        int arr[] = { 3, 4, 1 }, val = 5, n = 3;

        System.out.println(minCoins(arr, n, val));

    }
}

Minimum Jumps to reach at end

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int minJumps(int arr[], int n) {

        int dp[] = new int[n];
        int i, j;

        dp[0] = 0;

        for (i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (j = 0; j < i; j++) {
                if (i <= j + arr[j] && dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                    break;
                }
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        int arr[] = { 3, 4, 2, 1, 2, 1 }, n = 6;

        System.out.println(minJumps(arr, n));

    }
}

0-1 knapsack problem

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int knapSack(int W, int wt[], int val[], int n) {

        if (n == 0 || W == 0)
            return 0;

        if (wt[n - 1] > W)
            return knapSack(W, wt, val, n - 1);

        else
            return Math.max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
    }

    public static void main(String[] args) {
        int val[] = { 10, 40, 30, 50 };
        int wt[] = { 5, 4, 6, 3 };
        int W = 10;
        int n = 4;

        System.out.println(knapSack(W, wt, val, n));

    }
}

0-1 knapsack problem DP Solution

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int knapSack(int W, int wt[], int val[], int n) {

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

        for (int i = 0; i <= W; i++) {
            dp[0][i] = 0;
        }

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

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

        return dp[n][W];
    }

    public static void main(String[] args) {
        int val[] = { 10, 40, 30, 50 };
        int wt[] = { 5, 4, 6, 3 };
        int W = 10;
        int n = 4;

        System.out.println(knapSack(W, wt, val, n));

    }
}

Optimal Strategy for a Game

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int sol(int[] arr, int n) {
        int dp[][] = new int[n][n];

        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = Math.max(arr[i], arr[i + 1]);
        }

        for (int gap = 3; gap < n; gap = gap + 2) {
            for (int i = 0; i + gap < n; i++) {
                int j = gap + i;

                dp[i][j] = Math.max((arr[i] + Math.min(dp[i + 1][j], dp[i + 1][j - 1])),
                        (arr[i] + Math.min(dp[i + 1][j - 1], dp[i][j - 2])));
            }
        }

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

    public static void main(String[] args) {

        int n = 4;

        int arr[] = { 20, 5, 4, 6 };

        System.out.println(sol(arr, n));

    }
}

Egg Dropping Puzzle - Part 1

public class GFG {

    /*
     * Function to get minimum number of trials needed in worst case with n eggs and
     * k floors
     */
    static int eggDrop(int n, int k) {
        // If there are no floors, then
        // no trials needed. OR if there
        // is one floor, one trial needed.
        if (k == 1 || k == 0)
            return k;

        // We need k trials for one egg
        // and k floors
        if (n == 1)
            return k;

        int min = Integer.MAX_VALUE;
        int x, res;

        // Consider all droppings from
        // 1st floor to kth floor and
        // return the minimum of these
        // values plus 1.
        for (x = 1; x <= k; x++) {
            res = Math.max(eggDrop(n - 1, x - 1), eggDrop(n, k - x));
            if (res < min)
                min = res;
        }

        return min + 1;
    }

    // Driver code
    public static void main(String args[]) {
        int n = 2, k = 10;
        System.out.print("Minimum number of " + "trials in worst case with " + n + " eggs and " + k + " floors is "
                + eggDrop(n, k));
    }

}

Egg Dropping Puzzle - Part 2

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int res(int e, int f) {

        int dp[][] = new int[f + 1][e + 1];

        for (int i = 1; i <= e; i++) {
            dp[1][i] = 1;
            dp[0][i] = 0;
        }

        for (int j = 1; j <= f; j++) {
            dp[j][1] = j;
        }

        for (int i = 2; i <= f; i++) {
            for (int j = 2; j <= e; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int x = 1; x <= i; x++) {
                    dp[i][j] = Math.min(dp[i][j], 1 + Math.max(dp[x - 1][j - 1], dp[i - x][j]));
                }
            }
        }

        return dp[f][e];
    }

    public static void main(String[] args) {

        int n = 2;

        int f = 10;

        System.out.println(res(n, f));

    }
}

Count BSTs with n keys

A recursive structure is discussed, then a dynamic programming solution is discussed, finally relation with Catalan Numbers.

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int countBSTs(int n) {
        int dp[] = new int[n + 1];

        dp[0] = 1;

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

            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {

        int n = 4;

        System.out.println(countBSTs(n));

    }
}

Maximum sum with no two consecutive

DP-Code in O(1) space

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int maxSum(int arr[], int n) {
        if (n == 0)
            return arr[0];

        int prev_prev = arr[0];
        int prev = Math.max(arr[0], arr[1]);
        int res = prev;

        for (int i = 3; i <= n; i++) {
            res = Math.max(prev, prev_prev + arr[i - 1]);

            prev_prev = prev;

            prev = res;
        }

        return res;
    }

    public static void main(String[] args) {

        int n = 5, arr[] = { 10, 20, 30, 40, 50 };

        System.out.println(maxSum(arr, n));

    }
}

DP-Code in O(n) space

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int maxSum(int arr[], int n) {
        if (n == 0)
            return arr[0];

        int dp[] = new int[n + 1];

        dp[1] = arr[0];
        dp[2] = Math.max(arr[0], arr[1]);

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i - 1]);
        }

        return dp[n];
    }

    public static void main(String[] args) {

        int n = 5, arr[] = { 10, 20, 30, 40, 50 };

        System.out.println(maxSum(arr, n));

    }
}

Subset Sum Problem (Recursive Solution)

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int countSubsets(int arr[], int n, int sum) {
        if (n == 0)
            return sum == 0 ? 1 : 0;

        return countSubsets(arr, n - 1, sum) + countSubsets(arr, n - 1, sum - arr[n - 1]);
    }

    public static void main(String[] args) {

        int n = 3, arr[] = { 10, 20, 15 }, sum = 25;

        System.out.println(countSubsets(arr, n, sum));

    }
}

Subset Sum Problem (DP Solution)

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static int countSubsets(int arr[], int n, int sum) {
        int dp[][] = new int[n + 1][sum + 1];

        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        for (int j = 1; j <= sum; j++)
            dp[0][j] = 0;

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

        return dp[n][sum];
    }

    public static void main(String[] args) {

        int n = 3, arr[] = { 2, 5, 3 }, sum = 5;

        System.out.println(countSubsets(arr, n, sum));

    }
}

Matrix Chain Multiplication

/* A naive recursive implementation that simply follows 
the above optimal substructure property */
class MatrixChainMultiplication {
    // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
    static int MatrixChainOrder(int p[], int i, int j) {
        if (i + 1 == j)
            return 0;

        int min = Integer.MAX_VALUE;

        // place parenthesis at different places between first
        // and last matrix, recursively calculate count of
        // multiplications for each parenthesis placement and
        // return the minimum count
        for (int k = i + 1; k < j; k++) {
            int count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k, j) + p[i] * p[k] * p[j];

            if (count < min)
                min = count;
        }

        // Return minimum count
        return min;
    }

    // Driver program to test above function
    public static void main(String args[]) {
        int arr[] = new int[] { 40, 20, 30, 10, 30 };
        int n = arr.length;
        System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr, 0, n - 1));

    }
}

Matrix Chain Multiplication (DP Solution)

/* A naive recursive implementation that simply follows 
the above optimal substructure property */
class MatrixChainMultiplication {
    // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
    static int MatrixChainOrder(int p[]) {
        int n = p.length;
        int dp[][] = new int[n][n];
        for (int i = 0; i < n - 1; i++)
            dp[i][i + 1] = 0;

        for (int gap = 2; gap < n; gap++) {
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + p[i] * p[k] * p[j]);
                }
            }
        }

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

    // Driver program to test above function
    public static void main(String args[]) {
        int arr[] = new int[] { 40, 20, 30, 10, 30 };
        int n = arr.length;
        System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr));

    }
}

Palindrome Partitioning

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import static java.lang.System.out;

class GFG {

    static boolean isPalindrome(String input, int start, int end) {
        // Using two pointer technique to check pallindrome
        while (start < end) {
            if (input.charAt(start) != input.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }

    static int palPart(String str) {
        int n = str.length();

        int dp[][] = new int[n][n];

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

        for (int gap = 1; gap < n; gap++) {
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;

                if (isPalindrome(str, i, j)) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;

                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], 1 + dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

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

    public static void main(String[] args) {

        String s = "geek";

        System.out.println(palPart(s));

    }
}

Allocate Minimum Pages (Naive Method)

import java.util.*;
import java.io.*;
import java.lang.*;

class GFG {

    public static void main(String args[]) {
        int arr[] = { 10, 20, 10, 30 };
        int n = arr.length;
        int k = 2;

        System.out.print(minPages(arr, n, k));
    }

    public static int sum(int arr[], int b, int e) {
        int s = 0;
        for (int i = b; i <= e; i++)
            s += arr[i];
        return s;
    }

    public static int minPages(int arr[], int n, int k) {
        if (k == 1)
            return sum(arr, 0, n - 1);
        if (n == 1)
            return arr[0];
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            res = Math.min(res, Math.max(minPages(arr, i, k - 1), sum(arr, i, n - 1)));
        }
        return res;
    }
}

Allocate Minimum Pages (DP Solution)

import java.util.*;
import java.io.*;
import java.lang.*;

class GFG { 
    
    public static void main(String args[]) 
    { 
        int arr[]={10,20,10,30};
        int n=arr.length;
        int k=2;
        
    	System.out.print(minPages(arr,n,k)); 
    } 
    
    public static int sum(int arr[],int b, int e){
        int s=0;
        for(int i=b;i<=e;i++)
            s+=arr[i];
        return s;
    }
    
    public static int minPages(int arr[],int n, int k){
        int[][] dp=new int[k+1][n+1];
        for(int i=1;i<=n;i++)
            dp[1][i]=sum(arr,0,i-1);
        for(int i=1;i<=k;i++)
            dp[i][1]=arr[0];
            
        for(int i=2;i<=k;i++){
            for(int j=2;j<=n;j++){
                int res=Integer.MAX_VALUE;
                for(int p=1;p<j;p++){
                    res=Math.min(res,Math.max(dp[i-1][p],sum(arr,p,j-1)));
                }
                dp[i][j]=res;
            }
        }
        return dp[k][n];
    }
}