1 题目
来自算法导论的一道经典题目:
2 解答
动态规划原理
虽然已经用动态规划方法解决了上面问题,但是大家可能还跟我一样并不知道什么时候要用到动态规划。总结一下上面的斐波拉契数列和钢条切割问题,发现两个问题都涉及到了重叠子问题,和最优子结构。
①最优子结构
用动态规划求解最优化问题的第一步就是刻画最优解的结构,如果一个问题的解结构包含其子问题的最优解,就称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时,用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。
②重叠子问题
在斐波拉契数列和钢条切割结构图中,可以看到大量的重叠子问题,比如说在求fib(6)的时候,fib(2)被调用了5次,在求cut(4)的时候cut(0)被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题,不停的调用函数,而不是生成新的子问题。如果递归算法反复求解相同的子问题,就称为具有重叠子问题(overlapping subproblems)性质。在动态规划算法中使用数组来保存子问题的解,这样子问题多次求解的时候可以直接查表不用调用函数递归。
其实按我的理解:
(1)大问题能不能拆成小问题(没法拆成小问题,那还用什么动态规划。。。),小问题的解能不能推导出大问题的解(如果小问题推到不出大问题的解,那拆的还有什么意义呢?是不是)
(2)重复小问题(递归比如斐波那契,里边就有很多重复的递归操作比如 5 要求3和4,4 里边又要递归3 和2,计算3 重复了吧,很多的重复小问题,可以用备忘录也就是数组或者map缓存中间结果,或者自底向上的计算哈)
那么这个问题的解:我们用递归和动态规划来解一下:
2.1 递归
/** * 计算长度为 n 的钢条的最大收益 * @param map 长度收益映射表 * @param n 钢条长度 * @return 最大收益值 */ public static int maxIncome(int[] map, int n) { // 钢筋长度边界考虑 int res = 0; if (n <= 0) { return res; } // 递归的话 // n 的最大收益值 = 切割 n 次的最大收益(当 n = n 时,就是不切割的情况) for (int i = 1; i <= n; i++) { res = Math.max(res, map[i-1] + maxIncome(map, n - i)); } return res; } public static void main(String[] args) { int[] map = new int[]{1, 5 ,8, 9, 10, 17, 17, 20, 24, 30}; System.out.println(maxIncome(map, 4)); }
2.2 备忘录递归
/** * 计算长度为 n 的钢条的最大收益 * @param map 长度收益映射表 * @param n 钢条长度 * @return 最大收益值 */ public static int maxIncome(int[] map, int[] cache, int n) { // 钢筋长度边界考虑 int res = 0; if (n <= 0) { return res; } // 先从缓存中拿,因为钢筋收益肯定是大于0的,所以这里大于0就表示有计算过 if (cache[n] > 0) { System.out.println("命中缓存:" + n); return cache[n]; } // 递归的话 // n 的最大收益值 = 切割 n 次的最大收益(当 n = n 时,就是不切割的情况) for (int i = 1; i <= n; i++) { res = Math.max(res, map[i-1] + maxIncome(map, cache, n - i)); } cache[n] = res; return res; } public static void main(String[] args) { // 长度收益 int[] map = new int[]{1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; // 钢筋长度 int n = 4; // 缓存 int[] cache = new int[n + 1]; System.out.println(maxIncome(map, cache, n)); System.out.println(Arrays.toString(cache)); }
4里边会计算2,3里边也会计算2,所以2命中过一次
2.3 动态规划-自底向上
/** * 计算长度为 n 的钢条的最大收益 * @param map 长度收益映射表 * @param n 钢条长度 * @return 最大收益值 */ public static int maxIncome(int[] map, int n) { // 缓存 int[] cache = new int[n + 1]; // 自底向上 直接从1开始计算到n for (int i = 1; i <= n; i++) { int segRes = 0; for (int j = 1; j <= i; j++) { segRes = Math.max(segRes, map[j - 1] + cache[i - j]); } cache[i] = segRes; } return cache[n]; } public static void main(String[] args) { // 长度收益 int[] map = new int[]{1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; // 钢筋长度 int n = 4; System.out.println(maxIncome(map, n)); }
3 小结
好久没看动态规划了= =,适应中....也感谢铁子的讲解:https://blog.csdn.net/u013309870/article/details/75193592 讲的挺好。
标签:map,钢条,递归,int,问题,算法,动态,切割 From: https://www.cnblogs.com/kukuxjx/p/18015118