【困难】画匠问题－Java：解法二

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; /** * 画匠问题 * * 【题目】 * 给定一个整型数组arr，数组中的每个值都为正数，表示完成一幅画作需要的时间，再给定一个整数num表示画匠的数量，每个画匠只 * 能画连在一起的画作。所有的画家并行工作，请返回完成所有的画作需要的最少时间。 * * 【举例】 * arr=[3,1,4]，num=2。 * 最好的分配方式为第一个画匠画3和1，所需时间为4。第二个画匠画4，所需时间为4。因为并行工作，所以最少时间为4。如果分配方 * 式为第一个画匠画3，所需时间为3。第二个画匠画1和4，所需的时间为5。那么最少时间为5，显然没有第一种分配方式好。所以返回4。 * arr=[1,1,1,4,3]，num=3。 * 最好的分配方式为第一个画匠画前三个1，所需时间为3。第二个画匠画4，所需时间为4。第三个画匠画3，所需时间为3。返回4。 * * 【难度】 * 困难 * * 【解答】 * 方法一。如果只有1个画匠，那么对这个画匠来说，arr[0..j]上的画作最少时间就是arr[0..j]的累加和。如果有2个画匠，对他们 * 来说，画完arr[0..j]上的画作有如下方案： * 方案1：画匠1负责arr[0]，画匠2负责arr[1..j]，时间为Max{sum[0],sum[1..j]}。 * 方案2：画匠1负责arr[0..1]，画匠2负责arr[2..j]，时间为Max{sum[0..1],sum[2..j]}。 * ...... * 方案k：画匠1负责arr[0..k]，画匠2负责arr[k+1..j]，时间为Max{sum[0..k],sum[k+1..j]}。 * 方案j：画匠1负责arr[0..j-1]，画匠2负责arr[j]。时间为Max{sum[0..j-1],sum[j]}。 * 每一种方案其实都是一种划分，把arr[0..j]分成两部分，第一部分由画匠1来负责，第二部分由画匠2来负责，两部分的累加和哪个 * 大，哪个就是这种方案的所需时间。最后选所需时间最小的方案，就是答案。当画匠数量为i(i>2)时，假设dp[i][j]的值代表i个画 * 匠搞定arr[0..j]这些画所需的最少时间。那么有如下方案： * 方案1：画匠1~i-l负责arr[0]，画匠i负责arr[1..j]->max{dp[i-1][0],sum[1..j]}。 * 方案2：画匠1~i-1负责arr[0..1]，画匠i负责arr[2..j]->max{dp[i-1][1],sum[2..j]}。 * ...... * 方案k：画匠1~i-l负责arr[0..k]，画匠i负责arr[k+1..j]->max{dp[i-1,k],sum[k+1..j]}。 * 方案j：画匠1~i-1负责arr[0..j-1]，画匠i负责arr[j]->max{dp[i-1][j-1],sum[j]}。 * 哪种方案所需的时间最少，dp[i][j]的值就是那种方案所需的时间，即 * dp[i][j]=min{max{dp[i-1][k],sum[k+1..j]}(0<=k<j)} * 具体过程参见如下代码中的solution1方法，此方法使用动态规划常见的空间优化技巧。因为dp[i][j]的值仅依赖dp[i-1][..]的 * 值，所以我们不必生成规模为NumxN大小的矩阵，仅用一个长度为N的数组结构滚动更新、不断复用即可。 * 画匠数目为num，画作数量为N，所以一共是numxN个位置需要计算，每一个位罝都需要枚举所有的方案来找出最好的方案，所以方法一 * 的时间复杂度为O(N^2*num)。 * * 方法二，动态规划用四边形不等式优化后的解法。计算动态规划的每个值都需要去枚举，自然想到用"四边形不等式"及其相关猜想来做 * 枚举优化。具体地说，假设计算dp[i-1][j]时，在最好的划分方案中，第i-1个画匠负责arr[1..j]的画作。在计算dp[i][j+1] * 时，在最好的划分方案中，第i个画匠负责arr[m..j+1]的画作。那么在计算dp[i][j]时，假设最好的划分方案是让第i个画匠负责 * arr[k..j]，那么k的范围一定是[1,m]，而不可能在这个范围之外。四边形不等式的相关内容及其证明比较复杂且烦琐，本文因篇幅 * 所限，不再详述，有兴趣的读者可以自行学习。利用四边形不等式对枚举过程的优化可以将时间复杂度从O(N^2*num)降至O(N^2)。 * 具体过程请参看如下代码中的solution2方法。 * * @author Created by LiveEveryDay */ public class ArtisanPainterProblem2 { public static int solution2(int[] arr, int num) { if (arr == null || arr.length == 0 || num < 1) { throw new RuntimeException("err"); } int[] sumArr = new int[arr.length]; int[] map = new int[arr.length]; sumArr[0] = arr[0]; map[0] = arr[0]; for (int i = 1; i < sumArr.length; i++) { sumArr[i] = sumArr[i - 1] + arr[i]; map[i] = sumArr[i]; } int[] cands = new int[arr.length]; for (int i = 1; i < num; i++) { for (int j = map.length - 1; j > i - 1; j--) { int minPar = cands[j]; int maxPar = j == map.length - 1 ? j : cands[j + 1]; int min = Integer.MAX_VALUE; for (int k = minPar; k < maxPar + 1; k++) { int cur = Math.max(map[k], sumArr[j] - sumArr[k]); if (cur <= min) { min = cur; cands[j] = k; } } map[j] = min; } } return map[arr.length - 1]; } public static void main(String[] args) { int[] arr = {1, 1, 1, 4, 3}; int num = 3; System.out.printf("The result is: %d", solution2(arr, num)); } } // ------ Output ------ /* The result is: 4 */