算法体系-20 第二十节暴力递归到动态规划

前言 动态规划模型从尝试暴力递归到傻缓存到动态规划

四种模型和体系班两种模型一共六种模型

0.1 从左往右模型

0.2 范围讨论模型范围尝试模型 （这种模型特别在乎讨论开头如何如何 结尾如何如何）

玩家博弈问题，玩家玩纸牌只能那左或者右

0.3 样本对应样本对应模型（特别在乎两个样本结尾如何如何 最长公共子序列）

0.4 业务限制模型

动态规划只是暴力尝试的一个缓存
 

1.2 分析

到当前货物的时候有两种选择，要么选择当前货物，要么不选择当前货物

base 条件的判断分析

if (rest < 0) {

return -1;}

这里为什么不能取return 0，因为上由传下来的剩下的bags的重量要大于0上由的值才是有意义的；

递归改动态规划

第一步找确定的值

if (index == w.length) {

return 0;

}

第二步找动态的值喝确定值之间的关系，动态的值时如何根据静态值退出来的

int p1 = process(w, v, index + 1, rest);

int next = process(w, v, index + 1, rest - w[index]);

这辆动态函数都需要依赖他的一行，最后一行又是确定值

1.3 尝试递归代码

// 所有的货，重量和价值，都在w和v数组里// 为了方便，其中没有负数// bag背包容量，不能超过这个载重// 返回：不超重的情况下，能够得到的最大价值public static int maxValue(int[] w, int[] v, int bag) {if (w == null || v == null || w.length != v.length || w.length == 0) {return 0;}// 尝试函数！return process(w, v, 0, bag);}// index 0~N// rest 负~bagpublic static int process(int[] w, int[] v, int index, int rest) {if (rest < 0) {return -1;}if (index == w.length) {return 0;}//不选择当前的货物int p1 = process(w, v, index + 1, rest);int p2 = 0;//要选择当前的货物int next = process(w, v, index + 1, rest - w[index]);if (next != -1) {p2 = v[index] + next;}return Math.max(p1, p2);}

1.4 改动态规划

递归改动态规划

第一步找确定的值

第二步找动态的值喝确定值之间的关系，动态的值时如何根据静态值退出来的

改动态规划 看是否有重复的情况

下面的p（3，10）都会重复

1.5 动态规划代码

public static int dp(int[] w, int[] v, int bag) {if (w == null || v == null || w.length != v.length || w.length == 0) {return 0;}int N = w.length;int[][] dp = new int[N + 1][bag + 1];for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= bag; rest++) {int p1 = dp[index + 1][rest];int p2 = 0;int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];if (next != -1) {p2 = v[index] + next;}dp[index][rest] = Math.max(p1, p2);}}return dp[0][bag];}public static void main(String[] args) {int[] weights = { 3, 2, 4, 7, 3, 1, 7 };int[] values = { 5, 6, 3, 19, 12, 4, 2 };int bag = 15;System.out.println(maxValue(weights, values, bag));System.out.println(dp(weights, values, bag));}}