Dynamic Programming: Formulas and Patterns.

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

	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)