动态规划
1. 给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右上角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。如果给定的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
假设矩阵m的大小为M*N，行数为M，列数为N。生成大小和m
一样的矩阵dp，行数为M，列数为N，dp[i][j]的值表示从左上角，也就是（0，0）位置走到（i，j）位置的最小路径和。
dp[i][j]=m[i][j]+min{dp[i-1][j], dp[i][j-1]}
2. 给定数组arr，返回arr的最长递增子序列长度。比如arr=[2，1，5，3，6，4，8，9，7]，最长递增子序列为[1，3，4，8，9]，所以返回这个子序列的长度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]这个数结尾的情况下，arr[0,…i]中的最大递增子序列的长度。
dp[i]=max{dp[j]+1(0<=j<i, arr[j]<arr[i])}
3. 给定两个字符串str1和str2，返回两个字符串的最长公共子序列。例如，str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"或者"12C4B6"都是最长公共子序列，返回哪一个都行。
假设str1的长度为M，str2的长度为N，生成大小为M*N的矩阵dp。dp[i][j]的含义是str1[0...i]与str2[0...j]的最长公共子序列的长度。
dp求法如下：
- 矩阵dp第一列，即dp[i][0]，代表str1[0...i]与str2[0]的最长公共子序列长度，str2[0]只有一个字符，所以dp[i][0]最大为1.
一旦dp[i][0]被设为1，则令dp[i+1...M][0]全部为1 - 矩阵dp第一行，即dp[0][j]，与步骤1同理。
如果str1[0]==str2[j]，则令dp[0][j]为1
一旦dp[0][j]被设为1，则令dp[0][j+1...N]全部为1 - 其他位置，dp[i][j]的值只可能来自以下三种情况：
情况一：可能是dp[i-1][j]的值
情况二：同理可知，可能是dp[i][j-1]的值
情况三：如果str1[i]==str2[j]，还可能是dp[i-1][j-1]+1的值
三个最大的值，取一个即可。
4. 一个背包有一定的承重W，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。
假设物品编号从 1 到 n，一件一件物品考虑是否加入背包。
假设 dp[x][y] 表示前 x 件物品，在不超过重量 y 的时候的最大价值。枚举一下第 x 件物品的情况：
情况一：如果选第 x 件物品，则前 x - 1 件物品得到的重量不能超过 y - w[x]。
情况二：如果不选 x 件物品，则前 x - 1 件物品得到的重量不能超过 y。
无论哪种情况，我们都需要去求解 x - 1 件物品的情况。
所以，dp[x][y] 可能等于 dp[x-1][y]，也就是不取第 x 件物品的时候，价值和之前的一样。
也可能是 dp[x-1][y - w[x]] + v[x]，也就是决定拿第 x 件物品的情况，当然会加上 x 物品的价值。
两种可能性中，应该选择价值最大的那个，状态转移方程如下：
dp[x][y] = Max{dp[x-1][y], dp[x-1][y-w[x]]+v[x]}
对于 dp 矩阵来说，行数是物品的数量 n，列数是背包的最大承重 w。然后再从左到右，从上到下计算所有的 dp 的值即可。
该矩阵中的每个值的求解都代表一个更小的背包问题。
初始情况一：对于第0列，它的含义是背包的容量为0。此时物品的价值呢？没有。因此，第一列都填入0。
初始情况二：对于第0行，它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢？还是没有！所有都是0。
所以我们可以把这个矩阵的大小定义为 dp[n+1][y+1]，从第二行第二列也就是 dp[1][1] 的位置开始带入状态转移方程进行计算，其实这也解决了我长期以来对这个矩阵的行列都+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.定义状态矩阵，dp[i][j]表示在0..i个物品中不超过j重的情况下的背包的最大价值
int[][] dp = new int[A.length + 1][m + 1];
// 2.状态转移方程：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. 给定两个字符串str1和str2，在给定三个整数ic,dc和rc,分别代表插入、删除和替换一个 字符，返回将str1编辑成str2的最小代价。
解题方法：
动态规划。首先生成大小为(M+1)X(N+1)的矩阵dp。
假设str1="av=b12cd3", str2="abcdf"。dp[i][j]表示str1[0:i]编辑成str2[0:j]的最小代价。计算结果如下：
计算步骤：
1、dp[0][0]表示str1空的子串编辑成str2空的子串的代价为0
2、矩阵dp第一列即dp[0:M-1][0], dp[i][0] 表示str1[0:i-1]编辑成空串的最小代价，即把str1[0:i-1]中所有字符删掉的代价，所以dp[i][0] = dc * i
3、矩阵第一行即dp[0][0:N-1], dp[0][j]表示空串编辑成str2[0:j-1]的最小代价，即向空串中添加字符的代价，所以dp[0][j] = ic * j
4、其他位置，从左到右，从上到下计算，dp[i][j]的值可能来自于一下四种情况：
（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]的最小代价，那么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]的最小代价，那么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]的最小代价，那么dp[i][j]可能等于dp[i-1][j-1]+rc
（4）如果str1[i-1] == str2[j-1], 则此时dp[i][j] = dp[i-1][j-1]
以上四种可能的值中，选最小值作为dp[i][j]的值。
- 最终结果返回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]
}
