Hello，大家好，我是星恒
呜呜呜，今天给大家带来的又是一道经典的动归难题。
题目：leetcode 410
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k_ 个非空的连续子数组。
设计一个算法使得这 k _个子数组各自和的最大值最小。
示例：
示例 1：
输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2
输出：9
示例 3：
输入：nums = [1,4,4], k = 3
输出：4
提示：
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 106
- 1 <= k <= min(50, nums.length)
分析：
这次这道恐怖的困难题，就先和大家分享第一种动态规划的方法，第二种方法是二分 + 贪心，这里给大家附上答案，大家可以自行研究，后续有时间我会给大家补回来。
好，我来看如果使用动归来解这道题目：
这道题假设我们把它分为四段，我们可以枚举最后一段出现的位置k，然后来看是前面的情况的最大值大（前面的最大值通过递归来求，我们这里默认知道前面情况的最大值），还是最后一段的最大值大，从而得到这种k情况下的最大值。我们遍历k，看哪种情况的最大值最优（也就是最小）
那么前面情况的最大值如何求，其实步骤和上述一样。比如上述情况，我们需要前4点分成3段时的情况（也就是分成三段的最优情况），同理，再往前推我们需要知道分成两段的最优情况，这样，我们从开始一步一步推就可以了。
所以基本问题就变成了：求将i个数数分成j段的每种情况的最小最大数了
对于状态 f[i][j]，由于我们不能分出空的子数组，因此合法的状态必须有 i≥j。对于不合法（i<j）的状态，由于我们的目标是求出最小值，因此可以将这些状态全部初始化为一个很大的数。在上述的状态转移方程中，一旦我们尝试从不合法的状态 f[k][j−1]进行转移，那么 max(⋯ ) 将会是一个很大的数，就不会对最外层的 min{⋯ }产生任何影响。
此外，我们还需要将 f[0][0]的值初始化为 0。在上述的状态转移方程中，当 j=1 时，唯一的可能性就是前 i个数被分成了一段。如果枚举的 k=0，那么就代表着这种情况；如果 k≠0，对应的状态f[k][0] 是一个不合法的状态，无法进行转移。因此我们需要令 f[0][0]=0。
总结：「将数组分割为 mmm 段，求……」是动态规划题目常见的问法。
遇到这种分段的，除了要求将每一种情况列出来，使用回溯枚举每一种情况，一般都是动归
这种题的规律是：枚举每一段元素可能出现的元素，可能被分割成每种段数的情况
– 动归：现在的某种状态好，还是从以前直接弄过来的状态好
题解：
题解1：动态规划
class Solution {
public int splitArray(int[] nums, int m) {
int n = nums.length;
int[][] f = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(f[i], Integer.MAX_VALUE);
}
int[] sub = new int[n + 1];
for (int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + nums[i];
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, m); j++) {
for (int k = 0; k < i; k++) {
f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
}
}
}
return f[n][m];
}
}
题解2：二分 + 贪心
「使……最大值尽可能小」是二分搜索题目常见的问法。
class Solution {
public int splitArray(int[] nums, int m) {
int left = 0, right = 0;
for (int i = 0; i < nums.length; i++) {
right += nums[i];
if (left < nums[i]) {
left = nums[i];
}
}
while (left < right) {
int mid = (right - left) / 2 + left;
if (check(nums, mid, m)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean check(int[] nums, int x, int m) {
int sum = 0;
int cnt = 1;
for (int i = 0; i < nums.length; i++) {
if (sum + nums[i] > x) {
cnt++;
sum = nums[i];
} else {
sum += nums[i];
}
}
return cnt <= m;
}
}
如果大家有什么思考和问题，可以在评论区讨论，也可以私信我，很乐意为大家效劳。
好啦，今天的每日一题到这里就结束了，如果大家觉得有用，可以可以给我一个小小的赞呢，我们下期再见！
