什么是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]