Dynamic Programming: Formulas and Patterns.

(13). Weighted Job Scheduling.

Given certain jobs with start and end time and amount you make on finishing the job, find the maximum value you can make by scheduling jobs in non-overlapping way.

Formula:
Jobs [] = {(1,3), (2,5), (4,6), (6,7), (5,8), (7,9)};
Weights = {5, 6, 5, 4, 11, 2};
for (int i=0; i<jobs.len; i++) {
    for (int j=i+1; j<jobs.len; j++) {
       if (!overlap(jobs[i], jobs[j]) { 
          values[i] = Max (value[j], value[i] + weights[j]);
          parent[j] = i;
       }
    }
}

I0 = Iteration 0
I1 = Iteration 1 
etc..

Index ->	0	1	2	3	4	5
Jobs ->	(1, 3)	(2, 5)	(4, 6)	(6, 7)	(5, 8)	(7, 9)
weights ->	5	6	5	4	11	2
Iterations 0	5	6	10	9	16	7
I1	5	6	10	10	17	8
I2	5	6	10	14	17	12
I3	5	6	10	14	17	16
I4	5	6	10	14	17	16
Parents	-1	-1	-1	-1	-1	-1
I0	-1	-1	0	0	0	0
I1	-1	-1	0	1	1	1
I2	-1	-1	0	2	1	2
I4	-1	-1	0	2	1	3

• Time Complexity: O(n^2)
• Space Complexity: O(n)

(12). Rod Cutting Problem.

Given a rod of length n inches and an array of prices that contains prices of 
all pieces of size smaller than n. Determine the maximum value obtainable by 
cutting up the rod and selling the pieces. For example, if length of the rod 
is 8 and the values of different pieces are given as following, then the maximum 
obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)


length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 
(by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

Formula:
j <- rod length
len(i) <- rod of len i
val(i) <- value of rod of len i

if (j >= i) {
    T[i][j] = Max (
                    T[i-1][j], T[i][j-len(i)] + val(i);
                  )
} else {
    T[i][j] = T[i-1][j];
}

Example:
len [] = {1, 2, 3, 4};
prices [] = {2, 5, 7, 8};

target len = 5;

len(price)	0	1	2	3	4	5
1 (2)	0	2	4	6	8	10
2 (5)	0	2	5	7	10	12
3 (7)	0	2	5	7	10	12
4 (8)	0	2	5	7	10	12	<- max profit

• Time Complexity: O(len * size(rods))
• Space Complexity: O(len * size(rods))

(11). Egg Dropping.

Given some number of floors and some number of eggs, what is the minimum 
number of attempts it will take to find out from which floor egg will break.

Formula:
i <- egg
j <- floor

if (i > j) { //eggs > floors
    T[i][j] = T[i-1][j]
} else {
    // Min ( 1 + Max(Break case, No Break case) for all k in range of [1, j] )
    T[i][j] = 1 + Min (
                      Max (T[i-1][k-1], T[i][j-k] // 1 <= k <= j;
                      );

}

public int calculate(int eggs, int floors) {
		int T[][] = new int[eggs + 1][floors + 1];
		int c = 0;
		for (int i = 0; i <= floors; i++) {
			T[1][i] = i;
		}
		for (int e = 2; e <= eggs; e++) {
			for (int f = 1; f <= floors; f++) {
				T[e][f] = Integer.MAX_VALUE;
				for (int k = 1; k <= f; k++) {
					c = 1 + Math.max(T[e - 1][k - 1], T[e][f - k]);
					if (c < T[e][f]) {
						T[e][f] = c;
					}
				}
			}
		}
		return T[eggs][floors];
	}

(egg, floor)	1	2	3	4	5	6	7
1	0	1	2	3	4	5	6
2	0	1	2	2	2	3	3

• Time Complexity: (eggs * floors * floors)
• Space Complexity: (eggs * floors)

(10). Coin Changing: number of ways to get total.

Given a value N, if we want to make change for N cents, and we have infinite 
supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we 
make the change? The order of coins doesn’t matter.

For example, 
for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},
{1,1,2},{2,2},{1,3}. So output should be 4. 
For N = 10 and S = {2, 5, 3, 6}, 
there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. 
So the output should be 5.

Example:
coins[] = {2, 3, 4, 5}
total = 10;
*** please refer below matrix for trace with DP formula.

Formula:
j <- column
coins(i) <- row
If (j >= coins[i]) {
    T[i][j] = T[i-1][j] + T[i][j - coins[i]]);
} else {
    T[i][j] = T[i-1][j]
}

	0	1	2	3	4	5	6	7	8	9	10
2	1	0	1	0	1	0	1	0	1	0	1
3	1	0	1	1	1	1	2	1	2	2	2
4	1	0	1	1	2	1	3	2	4	3	5
5	1	0	1	1	2	2	3	3	5	5	7	<- Total Ways

• Time Complexity: O(Total * len(coins))
• Space Complexity: O(Total * len(coins))

(9). Longest Palindromic Subsequence.

Given a sequence, find the length of the longest palindromic subsequence in it. 
For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as 
“BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are 
also palindromic subsequences of the given sequence, but not the longest ones.

Formula:

for (int len=2; len<=size(S); len++) { 
 for (int i=0; i<=size(S)-len; i++) {
  int j = i + len - 1;
  if (S[i] == S[j]) {
     T[i][j] = Max (T[i][j], 2 + T[i+1][j-1])
  } else {
     T[i][j] = Max (T[i][j], T[i+1][j], T[i][j-1])
  }
 }
}

Indexes		0	1	2	3	4	5	6	7	8
	Char	B	B	A	B	C	B	C	A	B
0	B	1	2	2	3	3	5	5	5	7	<- longest palindrome
1	B		1	1	3	3	5	5	5	7
2	A			1	1	1	3	3	5	5
3	B				1	1	3	3	3	5
4	C					1	1	3	3	3
5	B						1	1	1	3
6	C							1	1	1
7	A								1	1
8	B									1

public int maxPalindromicSubsequence(int [] A) {
		if (A == null || A.length < 1) {
			return 0;
		}
		int [][] dp = new int[A.length][A.length];
		
		for (int i=0; i<A.length; i++) {
			dp[i][i] = 1;
		}
		
		for (int len=2; len<=A.length; len++) {
			for (int i=0; i<=A.length-len; i++) {
				int j = i + len -1;
				if (A[i] == A[j]) {
					dp[i][j] = Math.max(dp[i][j], 2 + dp[i+1][j-1]);
				} else {
					dp[i][j] = Math.max(dp[i][j], dp[i+1][j]);
					dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
				}
			}
		}
		return dp[0][A.length-1];
	}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

(8). Minimum Edit Distance.

Given two strings A & B and operations edit, delete and add, how many minimum 
operations would it take to convert string B to string A.

Formula:

if (A[i] == B[j]) {
    T[i][j] = T[i-1][j-1]
} else {
    T[i][j] = Min (T[i-1][j-1], T[i-1][j], T[i][j-1]) + 1
}

Example Strings:
A = COMMITER
B = COMPUTERS

Min Edit Distance (A, B) = 3

Indexes	0	C	O	M	P	U	T	E	R	S
0	0	1	2	3	4	5	6	7	8	9
C	1	0	1	2	3	4	5	6	7	8
O	2	1	0	1	2	3	4	5	6	7
M	3	2	1	0	1	2	3	4	5	6
M	4	3	2	1	1	2	3	4	5	6
I	5	4	3	2	2	2	3	4	5	6
T	6	5	4	3	3	3	2	3	4	5
E	7	6	5	4	4	4	3	2	3	4
R	8	7	6	5	5	5	4	3	2	3

• Time complexity is O(m*n)
• Space complexity is O(m*n)

(7). Optimal Binary Search Tree.

Given keys and frequency at which these keys are searched, how would you create 
binary search tree from these keys such that cost of searching is minimum.

Input:
      Keys[] = {10, 12, 16, 21}
frequency [] = {4, 2, 6, 3}

We take the bottoms up approach here and keep track of the cost of BST of
len=1 to len=size(A).

T[i][j] = Min (
              T[i][j],
              sum + min(T[i][k-1] + T[k+1][j]) for all i <= k <= j
              //where sum is Sum(freqency[i] .. frequency[j])
              );

• T[i][j] = cost(x) means total cost of BST with x as root

Index	0	1	2	3
Keys	10	12	16	21
Frequency	4	2	6	3
Index	0	1	2	3
0	4	8(0)	20(2)	26(2)
1		2	10(2)	16(2)
2			6	12(2)
3				3

//Formula and code below:

public int minCost(int [] keys, int [] freq) {
	int [][] T = new int[keys.length][keys.length];
		
	for(int i=0; i < T.length; i++){
            T[i][i] = freq[i];
        }
		
		for (int L=2; L <= keys.length; L++) {
			for (int i=0; i<=keys.length-L; i++) {
				int j = i + L -1;
				T[i][j] = Integer.MAX_VALUE;
				int sum = getSum(freq, i, j);
				for (int k=i; k<=j; k++) {
					int val = sum + (k-1 < i? 0: T[i][k-1]) + 
							(k+1 > j ? 0: T[k+1][j]);
					if (val < T[i][j]) {
						T[i][j] = val;
					}
				}
			}
		}
		
		return T[0][keys.length-1];
	}

        private int getSum(int [] freq, int i, int j) {
		int total = 0;
		for (int x=i; x<=j; x++) {
			total += freq[x];
		}
		return total;
	}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

(6). Longest Increasing Subsequence.

Find the longest increasing subsequence in an array.

Input:
int [] A = {3, 4, -1, 0, 6, 2, 3}

Output:
LIS: 4 (-1, 0, 2, 3)


Formula:
if (A[j] < A[i]) {
   T[i] = Max (T[i], T[j] + 1);
}

Time complexity: O(n^2)
Space complexity: O(n)


                int [] T = new int[A.length];
		for (int i=0; i<T.length; i++) {
			T[i] = 1;
		}
		
		for (int i=1; i<A.length; i++) {
			for (int j=0; j<i; j++) {
				if (A[j] < A[i]) {
					T[i] = Math.max(T[i], T[j] + 1);
				}
			}
		}

Input	3	4	-1	0	6	2	3
LIS - iteration0	1	1	1	1	1	1	1
LIS - iteration1	1	2	1	1	2	1	1	j=0	i=len(A)
LIS - iteration2	1	2	1	1	3	1	1	j=1	i=len(A)
LIS - iteration3	1	2	1	2	3	2	2	j=2	i=len(A)
LIS - iteration4	1	2	1	2	3	3	3	j=3	i=len(A)
LIS - iteration5	1	2	1	2	3	3	3	j=4	i=len(A)
LIS - iteration6	1	2	1	2	3	3	4	j=5	i=len(A)
Index	0	1	2	3	4	5	6
Parent-Iteration0	-1	-1	-1	-1	-1	-1	-1
Parent-Iteration1	-1	0	-1	-1	0	-1	-1
Parent-Iteration2	-1	0	-1	-1	1	-1	-1
Parent-Iteration3	-1	0	-1	2	1	2	2
Parent-Iteration4	-1	0	-1	2	1	3	3
Parent-Iteration5	-1	0	-1	2	1	3	3
Final LIS	4

(5). Coin Changing Minimum Coins.

Given a total and coins of certain denomination with infinite supply, what is the 
minimum number of coins it takes to form this total V.

int [] coins = {2, 3, 6, 7};
int V = 13;

Formula:
if (coins[i] >= j) {
   T[i][j] = Min (T[i-1][j], T[i][j-coins[i]]+1)
} else {
   T[i][j] = T[i-1][j]
}
OR
T[i] = Min(T[i], 1 + T[i - Coins[j]]
If we are maintaining one array to maintain min coin count and another array for
keeping track of parents.

refer here: coin change

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
2	0	inf	1	inf	2	inf	3	inf	4	inf	5	inf	6	inf
3	0	inf	1	1	2	2	2	3	3	3	4	4	4	5
6	0	inf	1	1	2	2	1	3	2	2	3	3	2	4
7	0	inf	1	1	2	2	1	1	2	2	2	3	2	2

• Time complexity - O(coins.size * total)
• Space complexity - O(coins.size * total)

(4). Subset Sum / Partition Problem.

Given an array of non negative numbers and a total, is there subset of numbers in this 
array which adds up to given total. Another variation is given an array is it possible 
to split it up into 2 equal sum partitions. Partition need not be equal sized. Just 
equal sum.

Input:
int [] A = {2, 3, 7, 8, 10}
int target = 11

Formula:
if (A[i] <= j) {
   T[i][j] = T[i-1][j-A[i]] || T[i-1][j]
} else {
   T[i][j] = T[i-1][j]
}

Time complexity - O(input.size * total_sum)
Space complexity - O(input.size * total_sum)

	0	1	2	3	4	5	6	7	8	9	10	11
2	T	F	T	F	F	F	F	F	F	F	F	F
3	T	F	T	T	F	T	F	F	F	F	F	F
7	T	F	T	T	F	T	F	T	F	T	T	F
8	T	F	T	T	F	T	F	T	T	F	T	T
10	T	F	T	T	F	T	F	T	T	F	T	T

(3). Matrix Chain Multiplication.

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is associative.     
In other words, no matter how we parenthesize the product, the result will be the same.     
For example, if we had four matrices A, B, C, and D, we would have:

    (ABC)D = (AB)(CD) = A(BCD) = ....
However, the order in which we parenthesize the product affects the number of simple arithmetic     
operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix,     
B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

    (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
    A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first parenthesization requires less number of operations.

Input:
int [] M = {2, 3, 6, 4, 5};
There are 4 matrices of dimensions (2, 3) (3, 6) (6, 4) and (4, 5)

Formula is:
T[i][j] = Min (
              T[i][k] + T[k][j] + (M[i] * M[k] * M[j]); //for i+1 <= k < j
          );

	0	1	2	3
0	0	36	84	124
1		0	72	132
2			0	120
3				0

	public int matrixMulChainCost(int [] M) {
		int len = M.length;
		
		/* m[i,j] = Minimum number of scalar multiplications needed
	       to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where 
	       dimension of A[i] is p[i-1] x p[i] */
	 
		int [][] T = new int[len][len];
		int value = 0;
		for (int n=2; n<len; n++) {
			for (int i=0; i<len-n; i++) {
				int j = i + n;
				T[i][j] = Integer.MAX_VALUE;
				for (int k=i+1; k<j; k++) {
					value = T[i][k] + T[k][j] + (M[i] * M[k] * M[j]);
					if (value < T[i][j]) {
						T[i][j] = value;
					}
				}
			}
		}
		return T[0][len-1];
	}

Time Complexity: O(n^3)
Space Complexity: O(n^2)

(2). Longest Common Subsequence.

Given two strings A & B, find longest common subsequence between them.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

	0	A	G	G	T	A	B
0	0	0	0	0	0	0	0
G	0	0	1	1	1	1	1
X	0	0	1	1	1	1	1
T	0	0	1	1	2	2	2
X	0	0	1	1	2	2	2
A	0	1	1	1	2	3	3
Y	0	1	1	1	2	3	3
B	0	1	1	1	2	3	4

Formula:

if (S1[i] == S2[j]) {
     T[i][j] = T[i-1][j-1] + 1;
} else {
     T[i][j] = Max (T[i-1][j], T[i][j-1]);
}

Time Complexity: O(n*m)
Space Complexity:O(n*m)

(1). 0/1 Knapsack problem

Given a bag with weight W and a list of items having a certain weight and value, how would you fill the bag so that you have maximum value?
Another variation of this problem is unbounded knapsack problem where an item can be repeated which is much simpler in the sense just take the value/weight ratio for each item then sort them in decreasing order and keep adding the item until you have no capacity left.

(Weight, Value)	0	1	2	3	4	5	6	7
(1, 1)	0	1	1	1	1	1	1	1
(3, 4)	0	1	1	4	5	5	5	5
(4, 5)	0	1	1	4	5	6	6	9
(5, 7)	0	1	1	4	5	7	8	9

Formula:

i denotes row and j column.

Row would be the list of items. wt(i),val(i)
Col would be weights from 0 to W (capacity of the bag).

If (wt[i] > j) {
	T[i][j] = T[i-1][j]
} else {
	T[i][j] = Max(
		      T[i-1][j - wt[i]] + val[i],
		      T[i-1][j]
                  );
}

*Time complexity - O(W*total items)