动态规划：空间优化技巧以及接龙型动态规划

关注行业动态，以便及时调整规划 #生活常识# #生活建议# #建议# #个人成长规划#

空间优化方法

滚动数组

如果状态依赖关系只在相邻的几层之间，则可以使用滚动数组进行优化
滚动数组可以让空间复杂度降维

坐标型动态规划使用滚动数组

数字三角形的状态转移方程为
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + A[i][j]

滚动数组优化之后为
dp[i % 2][j] = min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1]) + A[i][j]

因为每一步只与他的前一步有关，所以前面的数组我们可以重复使用，而不需要开辟新的空间。

随着滚动数组优化，我们需要改变的地方：

//原来的版本，详情请看动态规划入门： public int minimumTotal(int[][] triangle) { if (triangle == null || triangle.length == 0) { return -1; } if (triangle[0] == null || triangle[0].length == 0) { return -1; } int n = triangle.length; int[][] f = new int[n][n]; // initialize: 三角形的左边和右边要初始化 // 因为他们分别没有左上角和右上角的点 f[0][0] = triangle[0][0]; for (int i = 1; i < n; i++) { f[i][0] = f[i - 1][0] + triangle[i][0]; f[i][i] = f[i - 1][i - 1] + triangle[i][i]; } // function: f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j]; for (int i = 1; i < n; i++) { for (int j = 1; j < i; j++) { f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j]; } } // answer: 最后一层的任意位置都可以是路径的终点 int best = f[n - 1][0]; for (int i = 1; i < n; i++) { best = Math.min(best, f[n - 1][i]); } return best; } //滚动数组版本： public int minimumTotal(int[][] triangle) { if (triangle == null || triangle.length == 0) { return -1; } if (triangle[0] == null || triangle[0].length == 0) { return -1; } int n = triangle.length; //空间负责度进行了降纬 n => 2 int[][] f = new int[2][n]; f[0][0] = triangle[0][0]; // 因为数组空间不能够直接初始化，我们需要在动态的过程中初始化 for (int i = 1; i < n; i++) {f[i % 2][0] = f[(i - 1) % 2][0] + triangle[i][0];f[i % 2][i] = f[(i - 1) % 2][i - 1] + triangle[i][i]; for (int j = 1; j < i; j++) { f[i % 2][j] = min(f[(i - 1) % 2][j], f[(i - 1) % 2][j - 1]) + triangle[i][j] } } // answer: 最后一层的任意位置都可以是路径的终点 int best = f[(i - 1) % 2][0]; for (int i = 1; i < n; i++) { best = Math.min(best, f[(i - 1) % 2][i]); } return best; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

从上面的不同的两个版本我们可以知道最大的区别在于初始化，因为数组空间不能够直接初始化，所以我们需要在动态的过程中初始化。

那么能否两个维度一起滚动呢?
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + A[i][j] =>
dp[i % 2][j % 2] = min(dp[(i - 1) % 2][j % 2], dp[(i - 1) % 2][(j - 1) % 2]) + A[i][j]

不可以，因为j不是全局单调递增的，所以他的数据需要被保存，而 i 是全局单调递增的。

所以我们可以得出，滚动数组只可以滚动一个维度，不能滚动两个维度。

实例：
斐波那契数列

class Solution { public int fib(int n) { int[] dp = new int[3]; dp[0%3] = 0; dp[1%3] = 1; for(int i = 2 ; i <= n; i++){ dp[i % 3] = (dp[(i - 1) % 3] + dp[(i - 2) % 3]) % 1000000007; } return dp[n%3]; } } 123456789101112

总结：

滚动数组滚动的是第一重循环的变量，而不是第二重甚至第三重滚动数组也只能滚一个维度不能两个维度一起滚动

接龙型动态规划

属于“坐标型”动态规划的一种 题型一般是告诉你一个接龙规则，让你找最长的龙

经典例题：
LeetCode 300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

例子1: 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 12345

利用动规四要素分析：

state: dp[i] 表示以第 i 个数为龙尾的最长的龙有多长 function: dp[i] = max{dp[j] + 1}, j < i && nums[j] < nums[i] initialization://每个位置都可以是龙头 dp[0..n-1] = 1 answer: max{dp[0..n-1]} 1234567891011

Follow up: 求具体的方法

倒推法
记录每个状态的最优值是从哪个前继状态来的 通常需要一个和状态数组同样维度的数组 prev[i] 记录 使得 dp[i] 获得最优值的那个 j 是谁 j 是方程 dp[i] = max{dp[j] + 1} 里的j

最长上升连续子序列 II
描述：
给定一个整数矩阵. 找出矩阵中的最长连续上升子序列, 返回它的长度. 最长连续上升子序列可以从任意位置开始, 向上/下/左/右移动.

输入: [ [1, 2, 3, 4, 5], [16,17,24,23,6], [15,18,25,22,7], [14,19,20,21,8], [13,12,11,10,9] ] 输出: 25 解释: 1 -> 2 -> 3 -> 4 -> 5 -> ... -> 25 (由外向内螺旋) 12345678910

LeetCode 368.最大整除子集

描述：

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1: 输入: [1,2,3] 输出: [1,2] (当然, [1,3] 也正确) 1234

class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { if (nums == null || nums.length == 0) { return new ArrayList(); } Arrays.sort(nums); int n = nums.length; HashMap<Integer, Integer> dp = new HashMap(); HashMap<Integer, Integer> prev = new HashMap(); for (int i = 0; i < n; i++) { dp.put(nums[i], 1); prev.put(nums[i], -1); } int lastNum = nums[0]; for (int i = 0; i < n; i++) { int num = nums[i]; for (Integer factor : getFactors(num)) { if (!dp.containsKey(factor)) { continue; } if (dp.get(num) < dp.get(factor) + 1) { dp.put(num, dp.get(factor) + 1); prev.put(num, factor); } } if (dp.get(num) > dp.get(lastNum)) { lastNum = num; } } return getPath(prev, lastNum); } private List<Integer> getPath(HashMap<Integer, Integer> prev, int lastNum) { List<Integer> path = new ArrayList(); while (lastNum != -1) { path.add(lastNum); lastNum = prev.get(lastNum); } Collections.reverse(path); return path; } private List<Integer> getFactors(int num) { List<Integer> factors = new ArrayList(); if (num == 1) { return factors; } int factor = 1; while (factor * factor <= num) { if (num % factor == 0) { factors.add(factor); if (factor != 1 && num / factor != factor) { factors.add(num / factor); } } factor++; } return factors; } }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

网址：动态规划：空间优化技巧以及接龙型动态规划 https://www.yuejiaxmz.com/news/view/566656

相关内容

动态规划优化技巧.doc
动态规划之空间优化与总结回顾
二维动态规划空间优化
动态规划算法的优化技巧（转贴）
动态规划 多重01背包及空间开销优化
动态规划的时间复杂度优化
动态规划的优化与高级应用
动态规划的空间压缩技巧（降低空间复杂度）
算法动态规划01背包问题
国土空间规划背景下中国生态空间规划研究进展

随便看看