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