动态规划
0-1背包问题 --动态规划，放入n个物体按阶段处理，第n次的结果可以基于第n-1的结果来推导.
最大重量9，物体重量分别为 3，2，4，5
int[n][w]或int[w+1]解决

0-1背包升级版：
一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

先计算单价，先放入单价高的商品
有几个节点的 i 和 cw 是完全相同的，比如 f(2,2,4) 和f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，我们可以舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。也就是说，对于 (i, cw) 相同的不同状态，那我们只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑

动态规划理论
一个模型三个特征
一个模型：分阶段最优解模型
三个特征：
1）最优子结构，问题的最优解包含子问题的最优解；也可以通过子问题的最优解推导出问题的最优解
2）无后效性：在推导后面阶段的结果的时候，不关心当前结果怎么获取到的；某阶段的值确定后，就不受之后阶段的决策影响
3）重复子问题：决策序列达到相同阶段时，会产生重复的状态

解决动态规划：面对动态规划问题的时候能够有章可循，不会束手无策

注意：上面的分阶段最优解模型，一般用回溯算法也可以暴力解决，这个时候我们可以定义状态，每个状态代表一个节点；在递归树中展示，判断是否存在重复子问题，判断是否需要使用动态规划。

解决动态规划的两种思路：
1）状态转移表：如1-0背包问题，分别记录每一阶段后可能的结果，在该结果之上获取新的状态。
2）状态转移方程法：
状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。

1-0背包问题适合采用状态转移表，二维表最短路径问题适合状态转移方程，为什么？
因为二维路径问题中，到了某一点可能有多种方式，此时路径值也会有多个，因为此时到达方式不会影响后面的路径选择，此时就需要抛弃到达该点的非最佳方式，这就是状态转移方程的作用。
而1-0背包问题，到第n个物体时，并不知道此时最佳的方式，因为此时前面物体放入与否会决定后面物体的能否放入，此时并不能做出取舍；只能记录所有第n次的结果，之=这就是状态表的作用，依此退出第n+1次的重量。

动态规划实战
量化字符串的相似度：编辑距离
将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。

需要将源串，修改为目标串：
先找公共子串，确认目标串中哪些字符在源串中存在。
遍历源串，采取替换删除增加等操作：
公共字符，且位置相等，不处理，指针分别后移
非公共，源存在，目标不存在，源删除，源指针后移
非公共，源不存在，目标存在，源插入，源指针后移

如何查找公共子串
如 源cat 和目标cta，那我们可以认为公共子串是ct，方法为：
两指针分别指向c，比较相等后指针后移，源中a不存在a不是公共子串，源指针后移
t是公共子串

练习：如何采用回溯和动态规划实现求莱文斯坦距离？

编辑距离：源串和目的串都修改会复杂化逻辑；本质上都修改也可以也可以简化为仅仅修改源串的，这样能很大程度简化逻辑。
假设源串和目的串分别有一个指针在尾部，均向前移动，此时源串字符仅仅有三种处理：
删除字符：执行源字符的删除，源字符指针移动，但是两个指针指向的字符不一定相等，所以需要继续递归，编辑次数加一
替换或插入:执行源字符的替换和插入，此时插入或替换后的字符就是目的串指针对应的字符，所以一定会实现两个指针指向的字符不一定相等，所以均移动，编辑次数加一

public class DynamicPragraming {// 单个背包，有限制重量，从n个item中放入东西，求能放入的最大重量static int[] item = {3,2,4,7};static int[] value = {6,4,9,9};static int n = 4;static int maxWeight = 7;static int maxV = -1;// 背包升级版，质量不超过maxWeight时，求最大价值 -回溯算法public static void f(int i, int cw, int cv){if(i == n || cw == maxWeight){if(cv > maxV){maxV = cv;System.out.println(maxV);}return;}// 第i个不放入f(i+1, cw, cv);if(cw + item[i] <= maxWeight){f(i+1, cw+item[i], cv+value[i] );}}// 背包升级版，质量不超过maxWeight时，求最大价值 -动态规划算法public static int maxValue(int[] item, int[] value, int maxWeight){int itemNum = item.length;// state初始化,为什么一定要初始化为-1，而不是默认的0？？？int[][] state = new int[itemNum][maxWeight+1];for(int i=0; i<itemNum; i++){for(int j=0; j<maxWeight+1; j++){state[i][j]=-1;}}state[0][0] = 0;if(item[0]<=maxWeight){state[0][item[0]]=value[0];}for(int i=1; i<itemNum; i++){for(int j=0;j<=maxWeight;j++){// 第i个项目不放入，和i-1的价值相同state[i][j]=state[i-1][j];}// 第i个项目放入，和i-1的价值基础上增加
//            for(int weight=0;weight<=maxWeight;weight++){
//                if(weight+item[i]<=maxWeight && state[i-1][weight]>=0 ){
//                    // 新价值大于原本的价值才更新，否则不更新
//                    if(state[i-1][weight]+value[i] > state[i][weight+item[i]]){
//                        state[i][weight+item[i]]=state[i-1][weight]+value[i];
//                    }
//                }
//            }for(int weight=maxWeight-item[i];weight>=0;weight--){// i-1次放入时，只有价值大于零的才能继续放入if( state[i-1][weight]>=0 ){int newValue = state[i-1][weight] + value[i];// 放入后的价值大于原本价值才放入，否则不放入if(newValue > state[i][weight+item[i]]){state[i][weight+item[i]]=newValue;}}}}//  查找最大值for(int i=maxWeight; i>=0; i--){if(state[itemNum-1][i] >0){return state[itemNum-1][i];}}return 0;}public static int  findBackPack(int[] item, int maxWeight){int itemNum = item.length;// 如果int[i][j]=true;表示取到第i个item时，重量可以为jboolean[][] state= new boolean[itemNum][maxWeight+1];// 初始化state[0][0] = true;if(item[0] < maxWeight){state[0][item[0]]=true;}for(int i =1; i<itemNum; i++){for(int j=0; j<=maxWeight; j++){if(state[i-1][j]){// 第i个不放入state[i][j] = true;// 第i个放入if(j+item[i]<=maxWeight){state[i][j+item[i]] = true;}}}}for(int i=maxWeight; i>0; i-- ){if(state[itemNum-1][i]){return i;}}return 0;}public static int  findBackPackNew(int[] item, int maxWeight){int itemNum = item.length;// 如果int[i][j]=true;表示取到第i个item时，重量可以为jboolean[] state= new boolean[maxWeight+1];// 初始化state[0] = true;if(item[0] < maxWeight){state[item[0]]=true;}for(int i =1; i<itemNum; i++){// 仿照上面二维数组的错误写法
//            for(int j=0; j<=maxWeight; j++){
//                if(state[j]){
//                    // 存在bug，第一个item(值为3)后，0 3为true，
//                    // 第二个item(值为2)，先是j=0，所以新增2为true 然后在j=2的时候，会再次加2，4为true，此时明显2被加了两次是不正确的
//                    // 解决方案，就是在上面j的遍历进行递减遍历，因为值肯定是大于零的
//                    if(j + item[i] <= maxWeight){
//                        state[j+item[i]] = true;
//                        System.out.println("o");
//                    }
//                }
//            }// 正确且简介for(int j=maxWeight-item[i]; j>=0; j--){if(state[j]){state[j+item[i]] = true;}}}for(int i=maxWeight; i>0; i-- ){if(state[i]){return i;}}return 0;}public static void main(String[] args) {System.out.println(lwstNew(origin.length-1, dest.length-1));
//       lwst(0,0,0);
//        getShortestRoad(arr, 0,0,1);
//        System.out.println(dynamicShrotestRoad(arr,3,3));//        f(0, 0,0);
//        System.out.println(maxValue(item,value,7));
//        System.out.println(findBackPackNew(item, 8));
//        System.out.println(findBackPackNew(item, 7));
//        System.out.println(findBackPackNew(item, 6));
//        System.out.println(findBackPack(item, 8));
//        System.out.println(findBackPack(item, 7));
//        System.out.println(findBackPack(item, 6));}static int[][] arr = {{1,2,3,4},{3,4,4,1},{3,6,5,5},{6,6,2,5}};static int[][] road = new int[arr.length][arr.length];static int  minLength = Integer.MAX_VALUE;// n*n数组，从(0,0)到(n-1,n-1)的最短路径--状态转移方程法// 因为到达[i,j]有两种方式：[i-1,j]和[i][j-1]，// 如果是从i+1,j过来也可以，但此时因为绕行了，所以肯定不是最佳路径//所以状态转移方程minRoad[i,j]=min(road[i-1,j],road[i,j-1])+[i,j]public  static int dynamicShrotestRoad(int[][] arr, int row, int col){if(row >= arr.length || col >= arr.length){return -1;}if(row==0 && col==0){return arr[0][0];}else if(row == 0){return dynamicShrotestRoad(arr, row, col-1) + arr[row][col];}else if(col == 0){return dynamicShrotestRoad(arr, row-1, col) + arr[row][col];}else{return Math.min(dynamicShrotestRoad(arr, row-1, col),dynamicShrotestRoad(arr, row, col-1))+ arr[row][col];}}// n*n数组，从(0,0)到(n-1,n-1)的最短路径--回溯算法public static int getShortestRoad(int[][] arr, int row, int col, int value){if(col == arr.length-1 && row == arr.length-1){if(value < minLength){minLength = value;}System.out.println(minLength);}if(row <= arr.length-2){getShortestRoad(arr, row+1, col, value+arr[row+1][col]);}if(col <= arr.length-2){getShortestRoad(arr, row, col+1, value+arr[row][col+1]);}return 0;}static char[] origin = "mitcmu".toCharArray();static char[] dest = "mtacnu".toCharArray();static int minEditNum = Integer.MAX_VALUE;// 回溯法---解决两个字符串的编辑距离// 倒序比较，o:源字符串长度-1 d:目的字符串长的-1；// 调用方式：lwst(0,0,0);public static void lwst(int o, int d, int editNum){if(o>=origin.length-1 || d>=dest.length-1){if(editNum < minEditNum){minEditNum = editNum;}minEditNum = minEditNum+Math.abs(o-d);System.out.println(minEditNum);return;}if(origin[o] == dest[d]){lwst(o+1, d+1, editNum);}else{// 源插入 或者 源替换,此时执行后的结果一定是origin[o] == dest[d]lwst(o+1, d+1, editNum+1);// 源删除，此时结果不一定满足origin[o] == dest[d]，但是源肯定要前进一位lwst(o+1, d, editNum+1);}}// 状态转移方程---解决两个字符串的编辑距离// 倒序比较，o:源字符串长度-1 d:目的字符串长的-1// 调用方式：System.out.println(lwstNew(origin.length-1, dest.length-1));public static int lwstNew(int o, int d){// 如果源或目的已经到边界，此时只能插入。if( o < 0 || d < 0){return Math.abs(o-d);}// 字符相等此时直接移动指针，编辑次数无变化if(origin[d] == dest[o]){return lwstNew(o-1, d-1);}else{// 执行源字符的替换或插入，编辑次数加一，此时一定实现origin[d] == dest[o]，所以均移动int replaceOrInsert = lwstNew(o-1,d-1) + 1;// 执行源字符的删除，编辑次数加一，但是不确保origin[d] == dest[o-1]，所以需要继续递归int delete = lwstNew(o-1, d) + 1;return Math.min(replaceOrInsert, delete);}}
}