题目信息

LeetoCode地址: . - 力扣（LeetCode）

题目理解

将一个数组切k刀，每一块子数组求和，共k+1个数，这里面有一个最大的数Max。找一种切法，使这个Max最小。

暴力解法一定是会超时的，因为包含了大量的重复计算。

如果我们能够保存且借助已经算过的结果，在此基础上在更大范围的数组上计算，势必能节省更多的计算时间。这是动态规划的思路。

由于Max的取值上下限已知，上限是所有数的和，下限是最小的元素，如果我们能找到一种快速逼近结果的方法，也能够很快计算出结果，这是二分的思路。

动态规划写法

试想一下，在长度为[0,l]的数组上切k刀得到的Max，有可能通过哪些更小的，已经计算过的Max获得？

它有可能是[0,l-1]的数组上切k-1刀的Max，和第l个元素值的最小值。

它也有可能是[0,l-2]的数组上切k-1刀的Max，和第[l-1, l]这两个元素值之和里的最小值。

它也有可能是[0,l-3]的数组上切k-1刀的Max，和第[l-2, l]这三个元素值之和里的最小值。

。。。

归纳一下，如果我们用一个二维数组dp来保存求得的Max值，则

dp[l][k] = Math.min(dp[l][k], Math.max(dp([j, k-1], k-1), sum(l-j, l), j属于0到l-1.

我们只要从前向后，由短到长不断更新dp数组，最终求得到的dp[m][k]即是答案，其中m的长度是数组长度。

在实现上，要注意，当前数组可以切的刀数一定小于数组的长度。

另外，在求某一个子数组的和时，可以采用前缀和的方法减少计算量。

class Solution {public int splitArray(int[] nums, int k) {int l = nums.length;int[][] dp = new int[l+1][k+1];int[] prefixSum = new int[l+1];for (int i = 0; i<=l; i++) {Arrays.fill(dp[i], Integer.MAX_VALUE);}dp[0][0] = 0;for (int i = 1; i<=l; i++) {prefixSum[i] = prefixSum[i-1]+nums[i-1];}dp[0][0] = 0;for (int i = 1; i<=l; i++) {for (int j = 1; j<= Math.min(i, k);j++) {for (int m = 0; m < i; m++) {dp[i][j] = Math.min(dp[i][j], Math.max(dp[m][j-1], prefixSum[i]-prefixSum[m]));}}}return dp[l][k];}
}

二分+贪心写法

这种解法思路很无脑，即然我已经知道了上下限，那我就可以取中间值mid，并检查它在切k刀的前提下能够满足题意，如果满足，说明Max还可能更小，那就让上限变成mid,否则将下限变成mid+1.

至于检查的方法，则采用贪心的办法，即在当前子数组之和还小于mid的前提下，继续增加子数组的长度，直到不满足；重新开始一个子数组，直到遍历完所有数。 最后如果子数组数量小于等于题目的k，则说明mid是合法的。

class Solution {public int splitArray(int[] nums, int k) {int left = Integer.MAX_VALUE, right = 0;for (int num : nums) {right += num;left = Math.min(left, num);}while (left < right) {int mid = left + (right-left)/2;if (valid(nums, mid, k)) {right = mid;} else {left = mid+1;}}return right;}public boolean valid(int[] nums, int mid, int k) {int sum = 0;int cnt = 1;for (int num : nums) {if (sum + num > mid) {sum = num;if (sum > mid) {return false;}cnt++;} else {sum += num;}}return cnt <= k;}
}