分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; /** * 画匠问题 * * 【题目】 * 给定一个整型数组arr数组中的每个值都为正数表示完成一幅画作需要的时间再给定一个整数num表示画匠的数量每个画匠只 * 能画连在一起的画作。所有的画家并行工作请返回完成所有的画作需要的最少时间。 * * 【举例】 * arr[3,1,4]num2。 * 最好的分配方式为第一个画匠画3和1所需时间为4。第二个画匠画4所需时间为4。因为并行工作所以最少时间为4。如果分配方 * 式为第一个画匠画3所需时间为3。第二个画匠画1和4所需的时间为5。那么最少时间为5显然没有第一种分配方式好。所以返回4。 * arr[1,1,1,4,3]num3。 * 最好的分配方式为第一个画匠画前三个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[k1..j]时间为Max{sum[0..k],sum[k1..j]}。 * 方案j画匠1负责arr[0..j-1]画匠2负责arr[j]。时间为Max{sum[0..j-1],sum[j]}。 * 每一种方案其实都是一种划分把arr[0..j]分成两部分第一部分由画匠1来负责第二部分由画匠2来负责两部分的累加和哪个 * 大哪个就是这种方案的所需时间。最后选所需时间最小的方案就是答案。当画匠数量为i(i2)时假设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[k1..j]-max{dp[i-1,k],sum[k1..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[k1..j]}(0kj)} * 具体过程参见如下代码中的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][j1] * 时在最好的划分方案中第i个画匠负责arr[m..j1]的画作。那么在计算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 */