什么是DP? 簡單地來說就是把一個問題分解成兩個或者多個小問題。然后先把小的問題解出來，最后利用已經得到的答案，把大的問題解決。
它和分而治之有點類似，但有所不同。DP所分解出來的小問題會相互依賴，因此就不知道從哪里分。而分而治之的小問題不相互依賴。先看
個小程序吧，生成第n個Fibnacci數，可能有人會這么寫
int fib ( int n ) {
if ( n == 0 )
return 1;
if ( n == 1 )
return 1;
return fib ( n - 1 ) + fib ( n - 2 );
}
但這個函數是2^n的遞歸，所以很快堆棧就會被用完的。另外如果思考一下，你會發現 fib( n - 1 ) 也已經要用到fib ( n - 2 ), 可是在
算fib ( n ) 的時候，這個值又要算一遍，那為什么不把這個值存下來呢？
好, 我們就換個DP的方式：
int fib ( int n ) {
if ( n == 0 || n == 1 )
return 1;
int [] f = new int[ n ];
f[ 0 ] = 1;
f[ 1 ] = 1;
for( int i = 2; i < n; i++)
{
f[ i ] = f[ i-1 ] + f[ i-2 ];
}
return f[ n-1 ];
}
可能這個比較容易了。大家都明白，就是先把以前的值給算好，然后后面的計算就可以利用前面的值。嗯，那稍微換個難點的吧。給一個n*n的0,1 matrix，然后找到最大的全是1的submatrix的大小。比如：
00011
01111
11110
01110
這個最大的那個全是1的submatrix的大小就是3.看起來挺難，其實蠻容易的。
我們先用最平常的思路來解一下吧。
先初始化另外一個同樣大小的n*n的matrix
第一行和第一列很容易，和原先一樣的值
00011
0
0
1
0
接下來，算第二行，和其他的行。自己動手，你就知道其實就是
s[i][j] = min(s[i][j-1],s[i-1][j],s[i-1][j-1]) + 1
我們順便還可以加上一個max,記錄最大的值。
這樣這個就搞定了。DP介紹完畢。接下來開始關于String的DP
1.找到兩個字符串的最大相同字串的長度
例如：abaabb aabbaa 最大的相同字串aabb長度就是4.
解法：給兩個串 p,q 我們有
c(i,j) = 0 if p[i] != q[j]
c(i,j) = c(i-1,j-1) + 1 if p[i] = q[j].
代碼和上面submatrix很相似。先初始化邊緣，然后算出其他的值
2.找到兩個字符串的最大subsequence的長度
例如：acbbab abbca 最大的subsequence is abba 長度是4.
解法：給兩個串 p,q 我們有
c(i,j) = max(c(i-1,j),c(i,j-1)) if p[i] != q[j]
c(i,j) = c(i-1,j-1) + 1 if p[i] = q[j]
3.找到一個字符串最大的Palindrom
例如: abcdedcbdsa 最大的Palindrom就是bcdedcb 長度是7
解法：給一個串p
c(i,j) = max(c(i+1,j),c(i,j-1)) if p[i] != q[j]
c(i,j) = c(i+1,j-1) + 2 if p[i] = q[j]