動態(tài)規(guī)劃算法一般用來求解最優(yōu)化問題，當(dāng)問題有很多可行解饲常，而題目要求尋找這些解當(dāng)中的“最大值”/“最小值”時蹲堂，通常可以采用DP贝淤。
-
01背包問題
有n個重量和價值分別為wi柒竞，vi的物品。從這些物品中挑選出總重量不超過W的物品播聪，求所有挑選方案中價值總和的最大值朽基。
輸入
n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
W=5
----------
輸出
7
遞歸函數(shù)搜索
（1）有兩種可能:選或者不選；（2）使用遞歸离陶，在遍歷完n個數(shù)的時候稼虎，判斷價值最大。
int rec(int i,int j){//最初的j代表W
int res;
if(i==n){
//已經(jīng)沒有剩余物品了
res=0;
}
else if(j<w[i]){
//無法挑選這個物品
res=rec(i+1,j);
}
else{
//挑選和不挑選的這兩種情況都嘗試一下
res=max(rec(i+1,j), rec(i+1,j-w[i]) + v[i]);
}
return res;
}
動態(tài)規(guī)劃
記dp[i][j]為根據(jù)rec的定義招刨，直接利用遞推式和二重循環(huán)計算出各項的值
for(int i=n-1;i>=0;i--){ //i逆向進(jìn)行
for(int j=0;j<=W;j++){
if(j<w[i])
dp[i][j]=dp[i+1][j];
else
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}
}
關(guān)于狀態(tài)轉(zhuǎn)移方程的循環(huán)i方向問題霎俩，跟其遞推關(guān)系定義有關(guān)；如果是如下定義沉眶，則i的循環(huán)能正向進(jìn)行打却。
dp[i+1][j]=dp[i][j]; (j<w[i])
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); (其他)
個人理解總結(jié):
最重要就是動態(tài)轉(zhuǎn)移方程：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
/*
該問題可以描述為 “將前 i 件物品放入容量為 j 的背包中”；
問題可以轉(zhuǎn)換為“只考慮第 i 件物品的策略（放或不放）”谎倔，
如果不放第 i 件物品柳击，那么問題就轉(zhuǎn)化為 “前 i-1 件物品放入容量為 j 的背包中”;
如果放第 i 件物品，那么問題就轉(zhuǎn)化為“前 i ? 1 件物品放入剩下的容量為 v ? w[i] 的背包中”;此時獲得的最大價值就是 dp[i-1][j-w[i]]+v[i]
*/
具體實(shí)現(xiàn)：
//Time: O(nW) Memory: O(nW)
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int w[] = new int[n+1];
int v[] = new int[n+1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
int W = in.nextInt();
int dp[][] = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int j = W; j > 0; j--) {
if(j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] =
Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
System.out.println(dp[n][W]);
}
優(yōu)化空間復(fù)雜度：
如果只用一個數(shù)組 dp[W] 片习，能不能保證第 i
次循環(huán)結(jié)束后 dp[W] 中表示的就是我們定義的狀態(tài) dp[i,W] 呢捌肴？ dp[i,W] 是由 dp[i-1 ,W] 和
dp[i ? 1,W-w[i] ] 兩個子問題遞推而來蹬叭，能否保證在推 dp[i,W] 時（也即在第 i 次主循環(huán)中
推 dp[W] 時）能夠取用 dp[i ? 1,W] 和 dp[i ? 1,W? w[i] ] 的值呢？
事實(shí)上状知，這要求在每次主循環(huán)中我們以 重量 W 遞減順序計算 dp[W] 秽五，這樣才
能保證計算 dp[W] 時 dp[W? w[i] ] 保存的是狀態(tài) dp[i ? 1, W ? w[i]] 的值。
//Time: O(nW) Memory: O(W)
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int W = in.nextInt();
int w[] = new int[n+1];
int v[] = new int[n+1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
int dp[] = new int[W+1];
for (int i = 1; i <= n; i++) {
for (int j = W; j > 0; j--) {//關(guān)鍵所在
if(j < w[i])
dp[j] = dp[j];
else
dp[j] =
Math.max(dp[j],dp[j-w[i]]+v[i]);
}
}
System.out.println(dp[W]);
}
初始化細(xì)節(jié)：
我們看到的求最優(yōu)解的背包問題題目中试幽，事實(shí)上有兩種不太相同的問法筝蚕。有的題目
要求“恰好裝滿背包”時的最優(yōu)解卦碾，有的題目則并沒有要求必須把背包裝滿铺坞。一種區(qū)別
這兩種問法的實(shí)現(xiàn)方法是在初始化的時候有所不同。
如果是第一種問法洲胖，要求恰好裝滿背包济榨，那么在初始化時除了 F[0] 為 0 ，其它
F[1..V ] 均設(shè)為 ?∞ 绿映，這樣就可以保證最終得到的 F[V ] 是一種恰好裝滿背包的最優(yōu)解擒滑。
如果并沒有要求必須把背包裝滿，而是只希望價格盡量大叉弦，初始化時應(yīng)該將 F[0..V ]
全部設(shè)為 0 丐一。
-
最長公共子序列問題（LCS）
先科普下最長公共子序列 & 最長公共子串的區(qū)別： 找兩個字符串的最長公共子串，這個子串要求在原字符串中是連續(xù)的淹冰；而最長公共子序列則并不要求連續(xù)库车。
題目：給定兩個字符串s1s2...sn和t1t2...tn;求出這兩個字符串的最長公共子序列的長度。
輸入
n=4
m=4
s="abcd"
t="becd"
----------
輸出
3（"bcd"）
定義dp[i][j]為s1s2...sn和t1t2...tn的公共子序列的長度,再結(jié)合圖和代碼就很容易理解樱拴。
/*
問題可以轉(zhuǎn)換為 “s中的前i個字符與t中的前j個字符的公共子序列長度dp[i][j]”柠衍；
如果當(dāng)前s[i]==t[j],那么問題就轉(zhuǎn)變?yōu)?“s中的前i-1個字符與t中的前j-1個字符的公共子序列長度 dp[i-1][j-1]+1 ”；
如果不相等晶乔，那么問題的轉(zhuǎn)變就有兩種可能性珍坊；
（1）s中的前i個字符與t中的前j-1個字符的公共子序列長度dp[i][j-1]；
（2）s中的前i-1個字符與t中的前j個字符的公共子序列長度dp[i-1][j]正罢；
*/
int dp[][] = new int[n+1][m+1];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s[i-1]==t[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
}
}
System.out.println(dp[n][m]);
- 最長公共子串問題
最大公共子串長度問題就是：
求兩個串的所有子串中能夠匹配上的最大長度是多少阵漏。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最長的公共子串是"abcd",所以最大公共子串長度為4翻具。
//動態(tài)規(guī)劃
public class Main
{
static int f(String s1, String s2)
{
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = a[i-1][j-1]+1;
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
