动态规划：空间优化技巧以及接龙型动态规划 |
您所在的位置：网站首页 › 成语接龙句子 › 动态规划：空间优化技巧以及接龙型动态规划 |
|
空间优化方法
滚动数组
如果状态依赖关系只在相邻的几层之间，则可以使用滚动数组进行优化 滚动数组可以让空间复杂度降维 坐标型动态规划使用滚动数组数字三角形的状态转移方程为 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 for (int j = 1; j 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 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 public int fib(int n) { int[] dp = new int[3]; dp[0%3] = 0; dp[1%3] = 1; for(int i = 2 ; i dp[j] + 1}, j public List largestDivisibleSubset(int[] nums) { if (nums == null || nums.length == 0) { return new ArrayList(); } Arrays.sort(nums); int n = nums.length; HashMap dp = new HashMap(); HashMap prev = new HashMap(); for (int i = 0; i int num = nums[i]; for (Integer factor : getFactors(num)) { if (!dp.containsKey(factor)) { continue; } if (dp.get(num) lastNum = num; } } return getPath(prev, lastNum); } private List getPath(HashMap prev, int lastNum) { List path = new ArrayList(); while (lastNum != -1) { path.add(lastNum); lastNum = prev.get(lastNum); } Collections.reverse(path); return path; } private List getFactors(int num) { List factors = new ArrayList(); if (num == 1) { return factors; } int factor = 1; while (factor * factor factors.add(factor); if (factor != 1 && num / factor != factor) { factors.add(num / factor); } } factor++; } return factors; } } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |