做网站的分辨率要多大,wordpress添加支付教程,石家庄学设计的正规学校,做网站编程语言Hello#xff0c;大家好#xff0c;我是星恒 呜呜呜#xff0c;今天给大家带来的又是一道经典的动归难题。 题目#xff1a;leetcode 410给定一个非负整数数组 nums 和一个整数 k #xff0c;你需要将这个数组分成 k_ 个非空的连续子数组。设计一个算法使得这 k _个子数组… 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 10000 nums[i] 1061 k min(50, nums.length)
分析这次这道恐怖的困难题就先和大家分享第一种动态规划的方法第二种方法是二分 贪心这里给大家附上答案大家可以自行研究后续有时间我会给大家补回来。
好我来看如果使用动归来解这道题目这道题假设我们把它分为四段我们可以枚举最后一段出现的位置k然后来看是前面的情况的最大值大前面的最大值通过递归来求我们这里默认知道前面情况的最大值还是最后一段的最大值大从而得到这种k情况下的最大值。我们遍历k看哪种情况的最大值最优也就是最小
那么前面情况的最大值如何求其实步骤和上述一样。比如上述情况我们需要前4点分成3段时的情况也就是分成三段的最优情况同理再往前推我们需要知道分成两段的最优情况这样我们从开始一步一步推就可以了。
所以基本问题就变成了求将i个数数分成j段的每种情况的最小最大数了
对于状态 f[i][j]由于我们不能分出空的子数组因此合法的状态必须有 i≥j。对于不合法ij的状态由于我们的目标是求出最小值因此可以将这些状态全部初始化为一个很大的数。在上述的状态转移方程中一旦我们尝试从不合法的状态 f[k][j−1]进行转移那么 max(⋯ ) 将会是一个很大的数就不会对最外层的 min{⋯ }产生任何影响。
此外我们还需要将 f[0][0]的值初始化为 0。在上述的状态转移方程中当 j1 时唯一的可能性就是前 i个数被分成了一段。如果枚举的 k0那么就代表着这种情况如果 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;}
}如果大家有什么思考和问题可以在评论区讨论也可以私信我很乐意为大家效劳。好啦今天的每日一题到这里就结束了如果大家觉得有用可以可以给我一个小小的赞呢我们下期再见
