Dynamic Programming: Formulas and Patterns.

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