動(dòng)態(tài)規(guī)劃
1. 給定一個(gè)矩陣m田巴，從左上角開始每次只能向右或者向下走，最后到達(dá)右上角的位置遍搞，路徑上所有的數(shù)字累加起來(lái)就是路徑和较锡，返回所有的路徑中最小的路徑和。如果給定的m如大家看到的樣子伏钠，路徑1横漏，3，1熟掂，0缎浇，6，1赴肚，0是所有路徑中路徑和最小的素跺，所以返回12。
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
假設(shè)矩陣m的大小為M*N誉券，行數(shù)為M指厌，列數(shù)為N。生成大小和m
一樣的矩陣dp踊跟，行數(shù)為M踩验，列數(shù)為N，dp[i][j]的值表示從左上角，也就是（0晰甚，0）位置走到（i衙传，j）位置的最小路徑和。
dp[i][j]=m[i][j]+min{dp[i-1][j], dp[i][j-1]}
2. 給定數(shù)組arr厕九，返回arr的最長(zhǎng)遞增子序列長(zhǎng)度蓖捶。比如arr=[2，1扁远，5俊鱼，3，6畅买，4并闲，8，9谷羞，7]帝火，最長(zhǎng)遞增子序列為[1，3湃缎，4犀填，8，9]嗓违，所以返回這個(gè)子序列的長(zhǎng)度5.
arr：2 1 5 3 6 4 8 9 7
dp： 1 1 2 2 3 3 4 5 4
dp[i]表示在必須以arr[i]這個(gè)數(shù)結(jié)尾的情況下九巡，arr[0,…i]中的最大遞增子序列的長(zhǎng)度。
dp[i]=max{dp[j]+1(0<=j<i, arr[j]<arr[i])}
3. 給定兩個(gè)字符串str1和str2蹂季，返回兩個(gè)字符串的最長(zhǎng)公共子序列冕广。例如，str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"或者"12C4B6"都是最長(zhǎng)公共子序列偿洁，返回哪一個(gè)都行撒汉。
假設(shè)str1的長(zhǎng)度為M，str2的長(zhǎng)度為N涕滋，生成大小為M*N的矩陣dp神凑。dp[i][j]的含義是str1[0...i]與str2[0...j]的最長(zhǎng)公共子序列的長(zhǎng)度。
dp求法如下：
- 矩陣dp第一列何吝，即dp[i][0]，代表str1[0...i]與str2[0]的最長(zhǎng)公共子序列長(zhǎng)度鹃唯，str2[0]只有一個(gè)字符爱榕，所以dp[i][0]最大為1.
一旦dp[i][0]被設(shè)為1，則令dp[i+1...M][0]全部為1 - 矩陣dp第一行坡慌，即dp[0][j]黔酥，與步驟1同理。
如果str1[0]==str2[j]，則令dp[0][j]為1
一旦dp[0][j]被設(shè)為1跪者，則令dp[0][j+1...N]全部為1 - 其他位置棵帽，dp[i][j]的值只可能來(lái)自以下三種情況：
情況一：可能是dp[i-1][j]的值
情況二：同理可知，可能是dp[i][j-1]的值
情況三：如果str1[i]==str2[j]渣玲，還可能是dp[i-1][j-1]+1的值
三個(gè)最大的值逗概，取一個(gè)即可。
4. 一個(gè)背包有一定的承重W忘衍，有N件物品逾苫，每件都有自己的價(jià)值，記錄在數(shù)組v中枚钓，也都有自己的重量铅搓，記錄在數(shù)組w中，每件物品只能選擇要裝入背包還是不裝入背包搀捷，要求在不超過(guò)背包承重的前提下星掰，選出物品的總價(jià)值最大。
假設(shè)物品編號(hào)從 1 到 n嫩舟，一件一件物品考慮是否加入背包氢烘。
假設(shè) dp[x][y] 表示前 x 件物品，在不超過(guò)重量 y 的時(shí)候的最大價(jià)值至壤。枚舉一下第 x 件物品的情況：
情況一：如果選第 x 件物品威始，則前 x - 1 件物品得到的重量不能超過(guò) y - w[x]。
情況二：如果不選 x 件物品像街，則前 x - 1 件物品得到的重量不能超過(guò) y黎棠。
無(wú)論哪種情況，我們都需要去求解 x - 1 件物品的情況镰绎。
所以脓斩，dp[x][y] 可能等于 dp[x-1][y]，也就是不取第 x 件物品的時(shí)候畴栖，價(jià)值和之前的一樣随静。
也可能是 dp[x-1][y - w[x]] + v[x]，也就是決定拿第 x 件物品的情況吗讶，當(dāng)然會(huì)加上 x 物品的價(jià)值燎猛。
兩種可能性中，應(yīng)該選擇價(jià)值最大的那個(gè)照皆，狀態(tài)轉(zhuǎn)移方程如下：
dp[x][y] = Max{dp[x-1][y], dp[x-1][y-w[x]]+v[x]}
對(duì)于 dp 矩陣來(lái)說(shuō)重绷，行數(shù)是物品的數(shù)量 n，列數(shù)是背包的最大承重 w膜毁。然后再?gòu)淖蟮接艺炎浚瑥纳系较掠?jì)算所有的 dp 的值即可愤钾。
該矩陣中的每個(gè)值的求解都代表一個(gè)更小的背包問(wèn)題。
初始情況一：對(duì)于第0列候醒，它的含義是背包的容量為0能颁。此時(shí)物品的價(jià)值呢？沒有倒淫。因此伙菊，第一列都填入0。
初始情況二：對(duì)于第0行昌简，它的含義是屋內(nèi)沒有物品占业。那么沒有任何物品的背包里的價(jià)值多少呢？還是沒有纯赎！所有都是0谦疾。
所以我們可以把這個(gè)矩陣的大小定義為 dp[n+1][y+1]，從第二行第二列也就是 dp[1][1] 的位置開始帶入狀態(tài)轉(zhuǎn)移方程進(jìn)行計(jì)算犬金，其實(shí)這也解決了我長(zhǎng)期以來(lái)對(duì)這個(gè)矩陣的行列都+1的困擾念恍。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// 1.定義狀態(tài)矩陣，dp[i][j]表示在0..i個(gè)物品中不超過(guò)j重的情況下的背包的最大價(jià)值
int[][] dp = new int[A.length + 1][m + 1];
// 2.狀態(tài)轉(zhuǎn)移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1])
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i-1][j];
if (j >= A[i-1]) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
}
}
}
return dp[A.length][m];
}
}
6. 給定兩個(gè)字符串str1和str2晚顷，在給定三個(gè)整數(shù)ic,dc和rc,分別代表插入峰伙、刪除和替換一個(gè) 字符，返回將str1編輯成str2的最小代價(jià)该默。
解題方法：
動(dòng)態(tài)規(guī)劃瞳氓。首先生成大小為(M+1)X(N+1)的矩陣dp。
假設(shè)str1="av=b12cd3", str2="abcdf"栓袖。dp[i][j]表示str1[0:i]編輯成str2[0:j]的最小代價(jià)匣摘。計(jì)算結(jié)果如下：
計(jì)算步驟：
1、dp[0][0]表示str1空的子串編輯成str2空的子串的代價(jià)為0
2裹刮、矩陣dp第一列即dp[0:M-1][0], dp[i][0] 表示str1[0:i-1]編輯成空串的最小代價(jià)音榜，即把str1[0:i-1]中所有字符刪掉的代價(jià)，所以dp[i][0] = dc * i
3捧弃、矩陣第一行即dp[0][0:N-1], dp[0][j]表示空串編輯成str2[0:j-1]的最小代價(jià)赠叼，即向空串中添加字符的代價(jià)，所以dp[0][j] = ic * j
4违霞、其他位置嘴办，從左到右，從上到下計(jì)算买鸽，dp[i][j]的值可能來(lái)自于一下四種情況：
（1）str1[0:i-1]先編輯成str1[0:i-2]涧郊，即先刪除字符str1[i]，然后由str1[0:i-2]編輯成str2[0:j-1],dp[i-1][j] 表示str1[0:i-2]編輯成石頭人[0:j-1]的最小代價(jià)癞谒，那么dp[i][j]可能等于dc + dp[i-1][j]
（2）str1[0:i-1]可以先編輯成str2[0:j-2],然后向str2[0:j-2]插入字符str2[j-1],編輯成str2[0:j-1]底燎，dp[i][j-1]表示str1[0:i-1]編輯成str2[0:j-2]的最小代價(jià)，那么dp[i][[j]可能等于dp[i][j-1] + ic;
(3) 如果str1[i-1] != str2[j-1], 可以先將str1[0:i-2]編輯成str2[0:j-2],然后將str1[i-1]替換成str2[j-1]弹砚，dp[i-1][j-1]表示將str1[0:i-2]編輯成str2[0:j-2]的最小代價(jià)双仍，那么dp[i][j]可能等于dp[i-1][j-1]+rc
（4）如果str1[i-1] == str2[j-1], 則此時(shí)dp[i][j] = dp[i-1][j-1]
以上四種可能的值中，選最小值作為dp[i][j]的值桌吃。
- 最終結(jié)果返回dp最右下角的值朱沃。
func GetDp(str1, str2 []rune, ic, dc, rc int)int{
rows := len(str1) + 1
cols := len(str2) + 1
dp := make([][]int, rows)
for i, _ := range dp {
dp[i] = make([]int, cols)
}
for i:=0;i < cols;i++{
dp[0][i] = ic * i
}
for i:=0;i < rows;i++{
dp[i][0] = dc * i
}
for i:=1;i<rows;i++{
for j:=1;j<cols;j++{
if str1[i-1] == str2[j-1]{
dp[i][j] = dp[i-1][j-1]
}else{
dp[i][j] = dp[i-1][j-1] + rc
}
dp[i][j] = getMin(dp[i][j], dp[i][j-1]+ic)
dp[i][j] = getMin(dp[i][j], dp[i-1][j] + dc)
}
}
return dp[rows-1][cols-1]
}
