1. Longest Increasing Subsequence (LIS) problem
unsorted array, calculate out the maximum length of subsequence with non-decreasing order.
lis[i] = lis[j] + 1 if arr[i] > arr[j]; lis[i] is the lis with arr[i] as the last element. so to get the maximum for the whole array, we should iterate the array and find out the max(lis[i])
complexity: O(n^2)
better algorithm: O(n logn): http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
2. Longest common subsequence
f[i][j] = f[i-1][j-1]+1 if s1[i-1] == s2[j-1]
max(f[i-1][j], f[i][j-1]) else
3. edit distance
f[i][j] = f[i-1][j-1] if f[i-1] == f[j-1];
min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;
4. coin change
N cents, infinitely supply S = {S1, S2, ... Sm}, how many way to change it?
f[i][j] = f[i-s[j]][j] + f[i][j-1], i: the cents, j: using 0 to j Sj to change it.
5. matrix chain multiplication
for (L = 2; L < n; L++) { // L is the chain length
for (int i = 1; i <= n-L+1; i++) {
j = i+L-1;
m[i][j] = INT_MAX;
for (int k = i; k <= j-1; k++) {
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
m[i][j] = min(m[i][j], q);
}
}
}
return m[1][n-1];