常用十大算法_动态规划算法（DP）

动态规划算法（DP）

高能预警：DP算法不容易理解，需要动脑筋+查资料+找例题

动态规划算法（Dynamic Programming），是将复杂问题拆分成子问题，并在子问题的基础上，求解复杂问题，子问题之间不是独立的，而是相互依存的。

动态规划算法有两种实现形式：递归，非递归

有点莫名其妙对吧，下面以例子来了解（递归的容易，非递归的难，要有心理准备：<）

【例一】01背包问题：有个容量为4的背包，有以下3种物品，物品具有价值和重量属性，要求装入的物品价值总和最大且装入物品不能重复

解法1，递归实现动态规划算法

算法分析：

约定 weight[] 装载物品的重量，value[] 装载物品的价值。为了方便人机交互，定义上两个数字第一个元素为0。

装与不装，无非是受背包容量，和价格最大化限制。

我们假设 OPT(n,i) 代表对第n个物品操作且容量为i时的最优解（价值最大）。那么对于第n个物品而言，受背包容量限制：

当容量够的时候，我们有两种对n物品的操作，选n，不选n，选n时其对应最优解为 value[n]+OPT(n-1,i-weight[i])，不选n时其对应最优解为 OPT(n-1,i)。而此时 OPT(n,i)=MAX{value[n]+OPT(n-1,i-weight[i])，OPT(n-1,i)}

当容量不够时，我们只有一种对n物品的操作，即不选n。此时OPT(n,i)=OPT(n-1,i)

以上的运算流程是基于递归完成的。所以要设置递归结束条件：当n==0时，说明没有物品了，return 0;

根据以上推理得到该问题的状态转移方程（别被式子吓到了，这是纸老虎）

代码实现：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.dynamicProgramming;public class 动态规划算法_DP_01背包问题 {static int[] value={0,1500,3000,2000};//分别对应物品a,b,c，为了方便人机交互，定义第0个物品为0static int[] weight={0,1,4,3};//分别对应物品a,b,c，为了方便人机交互，定义第0个物品为0static int bag=4;//背包容量public static void main(String[] args) {System.out.println(re_OPT(3,4));}/*** 动态规划：递归来求最优解* @param n 第n个物品* @param bag 背包容量* @return 最优解*/public static int re_OPT(int n, int bag){if (n==0){return 0;}if (bag>=weight[n]){return Math.max(value[n]+ re_OPT(n-1,bag-weight[n]), re_OPT(n-1,bag));}else {return re_OPT(n-1,bag);}}}

递归式实现了，仍然存在有个小问题。

递归的本身设计，就包含了大量的重复计算，如上图，相同颜色的方框，表示重复运算。这在海量数据计算过程中，由于递归将创建大量的栈空间，进行重复运算。极易引发栈溢出。为了解决这一问题，需要彻底改变运算模式-------非递归动态规划

解法2，非递归实现动态规划算法

算法分析：

将题目中的信息全部整合到一个二维表中，该表对应了容量从4到0的各种情况下的最优解。

表的第一行，由于价值为0，所以全是0。表的第一列，由于容量为0，所以全是0。

其他的情况，需要通过程序进行求解。每一个空都对应一种情况，每种情况都受容量限制，每种情况都有两种操作（选与不选）。

与解法1不同的是，这里是自底而上求解（表中从左至右，从上至下）。将每次计算的结果保存在二维数组中，求解的下一个结果依赖于上一次已经求好的结果。这就解决了递归式重复计算的问题。

最终的答案，就在二维数组的右下角。

代码实现：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.dynamicProgramming;public class 动态规划算法_DP_01背包问题 {static int[] value={0,1500,3000,2000};//分别对应物品a,b,c，为了方便人机交互，定义第0个物品为0static int[] weight={0,1,4,3};//分别对应物品a,b,c，为了方便人机交互，定义第0个物品为0static int bag=4;//背包容量public static void main(String[] args) {System.out.println(dp_OPT(3,4));}/*** 动态规划：非递归求最优解* @param n 第n个物品* @param bag 背包容量* @return 最优解*/public static int dp_OPT(int n, int bag){int[][] result=new int[weight.length][bag+1];//创造一个二维数组，用来存放各种情况对应的最优解,前[]保存第几个物品，后面[]保存多少背包容量//将第一行与第一列重置为0for (int i=0;i<result[0].length;i++){result[0][i]=0;}for (int j=0;j<result.length;j++){result[j][0]=0;}for (int i=1;i<result.length;i++){for (int j=1;j<result[0].length;j++){result[i][j] = j>=weight[i]?Math.max(value[i]+result[i-1][j-weight[i]],result[i-1][j]):result[i-1][j];}}return result[n][bag];}}

【例二】 求相隔数据和最大值：有数据 {5,7,3,1,4,2} 需要间隔式的取出几个数使数之和最大，求出最大值。

代码实现：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.dynamicProgramming;public class 动态规划算法_DP_相隔数据和最大 {public static void main(String[] args) {int[] data=new int[]{5,7,3,1,4,2};System.out.println(re_OPT(data,5));System.out.println(dp_OPT(data,5));}/*** 动态规划：递归式计算出最优解* @param data 需要求解的数据* @param i 在第i个数据前进行最优解计算* @return 返回最优解*/public static int re_OPT(int[] data, int i){if (i==0){//i==0时，第一个数据本身就是最优解。递归终止条件return data[0];}else if (i==1){//i==1是，前两个数中的最大值就是最优解。递归终止条件return Math.max(data[0],data[1]);}else {int A= re_OPT(data,i-2)+data[i];//A方案：选当前数据int B= re_OPT(data,i-1);//B方案：不选当前数据return Math.max(A,B);//在AB方案中，返回最大值作为最优解}}/*** 动态规划：非递归计算出最优解* @param data 需要求解的数据* @param i 在第i个数据前进行最优解计算* @return 返回最优解*/public static int dp_OPT(int[] data, int i){int[] opt=new int[data.length];int A;int B;opt[0]=data[0];opt[1]=Math.max(data[0],data[1]);for (int j=2;j<data.length;j++){A=opt[j-2]+data[j];//A方案：选当前数据B=opt[j-1];//B方案：不选当前数据opt[j]=Math.max(A,B);}return opt[i];}
}

12
12

【例三】数据求和匹配：{3,34,4,12,5,2}的数据中，给出一个待匹配的值n，问是否能从数据中任意取出几个数，使得之和等于n ?

代码实现：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.dynamicProgramming;public class 动态规划算法_DP_数据求和匹配 {static int[] data={3,34,4,12,5,2};public static void main(String[] args) {System.out.println(re_OPT(data.length-1,9));System.out.println(re_OPT(data.length-1,13));System.out.println(dp_OPT(data.length-1,9));}/*** 动态规划：递归求出在一组数据中，是否有相加之和为待匹配数的情况* @param i 数组索引* @param a 待匹配数* @return true or false*/public static boolean re_OPT(int i, int a){if (a==0){//终止递归return true;}else if (i==0){//终止递归return data[i]==a;}else if (data[i]>a){//剪枝return re_OPT(i-1,a);}return re_OPT(i-1,a-data[i])|| re_OPT(i-1,a);//两种方案，选与不选}/*** 动态规划：非递归出在一组数据中，是否有相加之和为待匹配数的情况* @param i 数组索引* @param a 待匹配数* @return true or false*/public static boolean dp_OPT(int i, int a){boolean[][] res=new boolean[data.length][a+1];boolean A,B;for (int x=0;x<res.length;x++){for (int y=0;y<a+1;y++){if (y==0){res[x][y]=true;}if (x==0 && y==data[0]){res[x][y]=true;}}}for (int x=1;x<res.length;x++){for (int y=1;y<a+1;y++){if (data[x]>y){res[x][y]=res[x-1][y];}else {A=res[x-1][y-data[x]];B=res[x-1][y];res[x][y]=A||B;}}}return res[i][a];}
}

true
false
true

【例四】最优收益问题：如下图，8个任务分布在0~11的时间段内，每个任务对应的收益不同，（1号任务，收益5），在一个时间段内只能做一件任务。问在8个任务中最优收益为多少？

代码实现：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.dynamicProgramming;
public class 动态规划算法_DP_最优收益问题 {static int[][] taskTime={{0,0},{1,4},{3,5},{0,6},{4,7},{3,8},{5,9},{6,10},{8,11}};//存储任务时长static int[] income={0,5,1,8,4,6,3,2,4};//存储任务收益public static void main(String[] args) {System.out.println(OPT(8));}/*** 动态规划：递归计算出最优解* @param i 开始计算的任务序号* @return 最优解*/public static int OPT(int i){if (i==0){//当i为1时，说明已经完成规划内的任务，停止递归return 0;}int A=income[i]+OPT(prev(i));//方案1：选择当前任务int B=OPT(i-1);//方案2：不选择当前任务return Math.max(A,B);//求最优解}/*** 根据任务时长获取当前任务之前的最近可用任务* @param i 当前任务* @return 最近可用任务*/public static int prev(int i){int value=taskTime[i][0];while (true){if (i==1){return 0;}if (value>=taskTime[i-1][1]){return i-1;}i--;}}
}