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];
}
}