Dynamic Programming: Formulas and Patterns.

(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)