本文主要是介绍Leetcode 410 分割数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目信息
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;}
}这篇关于Leetcode 410 分割数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
