前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
给定一个正整数数组和一个num，其中arr[i]代表第i幅画画完所需要的时间，num代表画匠的数量。每一个画匠如果选择了一幅画，则必须画完为止，其他画匠不允许帮其画。求num个画匠完成arr中的画最少需要多少时间
解决方案
暴力递归
略
动态规划：
要素一：dp[i][j]代表 i个画匠完成 arr[0…j]幅画所需要的最少时间
要素二：dp[i][j] 的计算方式：
· 游标k从j到0，依次代表 arr[k…j]由第一个画匠完成，剩下的arr[0…k]由剩下的i-1个画匠完成，求所有可能性中的最小值即可
四边形不等式优化动态规划
在原动态规划基础上，限制第三层循环尝试的x的范围：
·如果dp[i-1][j]获取到最少的时间时，此时k值记录为l，后面计算dp[i][j]时，k值将不再小于l
·如果dp[i][j+1]获取到最少时间时，此时k值记录为r，后面计算dp[i][j]时，k值将不再大于r
根据以上两点可以确定尝试x的范围在[l…r]，具体四边形不等式的证明非常多，这里不再证明
最优解
最优解还是提取三个变量，
1、画匠数量
2、arr
3、最少时间
将问题”num个画匠完成arr需要的最少时间“转化为”时间限制time下，完成arr，最少需要的画匠数量“
当arr有一个超过限制，则画匠数量再多都不能完成，因为一幅画必须只能一个画匠完成
那么time的范围是什么呢？time的最小值从0开始，最大值为arr中所有的元素的和，因为如果只有一个画匠，则time就是所有元素的和，也是所需要的时间的最大值
ok，现在只需要遍历time的每一个值作为限制，完成arr，所需要的最少画匠刚好超过num时，time是多少就是答案！
代码编写
java语言版本
基本动态规划：
/**
* 二轮测试：普通动态规划
* @param arr
* @param num
* @return
*/
public static int solution1Cp1(int[] arr, int num) {
if (arr == null || num == 0) {
return -1;
}
// dp[i][j]代表i个画匠解决arr[0...j]个画所需要的最少时间
int[][] dp = new int[num+1][arr.length];
// 初始化
dp[1][0] = arr[0];
// 完成一个花匠需要的时间
for (int j = 1; j < dp[0].length; j++) {
dp[1][j] = dp[1][j-1] + arr[j];
}
for (int i = 2; i < num + 1; i++) {
dp[i][0] = arr[0];
for (int j = 1; j < dp[0].length; j++) {
// 开始分配让[k...j]给到一个人完成，剩下的[0...k]让i-1个人完成即可,所需要的最少时间
int tmp = 0;
int min = Integer.MAX_VALUE;
for (int k = j-1; k >= 0; k--) {
// 当前人干
tmp += arr[k+1];
// 剩下人干
int n1 = dp[i-1][k];
min = Math.min(Math.max(tmp, n1), min);
}
dp[i][j] = min;
}
}
return dp[num][arr.length-1];
}
四边形不等式优化动态规划
/**
* 二轮测试：四边形不等式优化
* @param arr
* @param num
* @return
*/
public static int solution2Cp2(int[] arr, int num) {
if (arr == null || num == 0) {
return -1;
}
// dp[i][j]代表i个画匠解决arr[0...j]个画所需要的最少时间
int[][] dp = new int[num+1][arr.length];
// map[i][j]代表当前状态下最优解时的k值是多少
int[][] map = new int[num+1][arr.length];
// 初始化
dp[1][0] = arr[0];
// 完成一个花匠需要的时间
for (int j = 1; j < dp[0].length; j++) {
dp[1][j] = dp[1][j-1] + arr[j];
}
for (int i = 2; i < num + 1; i++) {
dp[i][0] = arr[0];
for (int j = arr.length-1; j >= 0; j--) {
// 开始分配让[k...j]给到一个人完成，剩下的[0...k]让i-1个人完成即可,所需要的最少时间
int min = Integer.MAX_VALUE;
// 增加一个范围确定
int l = map[i-1][j];
// 如果是最右边的j，则直接赋值为j，也就是最大范围，这个说明右边无界限
int r = j == arr.length-1 ? j : map[i][j+1];
int tmp = getTmp(arr, r, j);
int k = r-1;
int mink = -1;
for (; k >= l; k--) {
// 当前人干
tmp += arr[k+1];
// 剩下人干
int n1 = dp[i-1][k];
if (Math.max(tmp, n1) < min) {
min = Math.max(tmp, n1);
mink = k;
}
dp[i][j] = min;
map[i][j] = mink;
}
}
}
return dp[num][arr.length-1];
}
最优解
/**
* 方法三：最优解
* 二分法求
* @param arr
* @param num
* @return
*/
public static int solutionCp3(int[] arr, int num) {
if (arr == null || num == 0) {
return -1;
}
if (num >= arr.length) {
// 花匠数超过了
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
return max;
}else {
int minSum = 0;
int maxSum = 0;
for (int i = 0; i < arr.length; i++) {
maxSum += arr[i];
}
// 这里如果不-1会无限死循环
while (minSum < maxSum-1) {
// 求中间值作为时间限制
int mid = (minSum + maxSum)/2;
if (getNeedNumCp1(arr, mid) > num) {
// 所需要的花匠多于num,调高限度
minSum = mid;
}else {
maxSum = mid;
}
}
return maxSum;
}
}
/**
* 规定每一个花匠时间不能超过limit，则最少需要多少个画匠
* @param arr
* @param limit
* @return
*/
private static int getNeedNumCp1(int[] arr, int limit) {
int res = 1;
int tem = 0;
for (int i = 0; i < arr.length; i++) {
// 有一幅画超过了就算不可能完成的
if (arr[i] > limit) {
return Integer.MAX_VALUE;
}
if (tem + arr[i] > limit) {
tem = arr[i];
res++;
}else {
tem += arr[i];
}
}
return res;
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
最优解我觉得如果仔细想想还是和丢棋子问题的最优解存在相似之处的，这类问题总结一下首先需要提炼出三个变量：
1、要解决问题的工具 如： 石子数量（画匠数量）
2、要解决的问题 ，如 ：层高（画arr）
3、需要的最少开销，如：最少次数（最少时间）
这类场景在我们的业务中经常会遇到，所以其实这类动态规划对于业务来讲，还是很有用的，比如我们业务中存在不同规格的授权，但是授权可以组合成一个大的授权来满足用户的一个大的授权需求，如何能够使用最少的授权来满足当前场景，这类问题层出不穷，首先动态规划和四边形不等式都是最基本的解法，最后就是最优解的思路
首先动态规划解决的问题是：使用 ”要解决问题的工具“来解决”问题“所需要的”最少开销“
而最优解解决的问题时：在有限的”开销下“，要搞定”问题“，最少需要多少”工具“?
而开销则需要确定一个范围，比如丢棋子，丢多少次能一定确定？层高多少，就需要最多丢多少次
比如画匠问题需要最多多少时间做完？一个画匠画完arr所需要的时间就是time的最大值
确定了开销的范围之后，从小到大遍历开销即可解决问题。