?LeetCode刷題實戰(zhàn)410：分割數(shù)組的最大值
Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m subarrays.
示例
示例 1：
輸入：nums = [7,2,5,10,8], m = 2
輸出：18
解釋：
一共有四種方法將 nums 分割為 2 個子數(shù)組。其中最好的方式是將其分為 [7,2,5] 和 [10,8] 。
因為此時這兩個子數(shù)組各自的和的最大值為18，在所有情況中最小。
示例 2：
輸入：nums = [1,2,3,4,5], m = 2
輸出：9
示例 3：
輸入：nums = [1,4,4], m = 3
輸出：4
解題
class?Solution?{
????public?int?splitArray(int[] nums, int?m) {
??if?(nums == null?|| nums.length < m) return?-1;
??int?n = nums.length;
??// dp[i][j] 表示nums[0..i]劃分成j段時的最小情況
??int[][] dp = new?int[n + 1][m + 1];
??for?(int?i = 0; i <= n; i++) {
????Arrays.fill(dp[i], Integer.MAX_VALUE);
??}
??// sub[i]表示num[0..i]的和
??int[] sub = new?int[n + 1];
??for?(int?i = 0; i < n; i++) {
????sub[i + 1] = sub[i] + nums[i];
??}
??// 初始條件
??dp[0][0] = 0;
??for?(int?i = 1; i <= n; i++) {
????// 由于我們不能分出空的子數(shù)組，所以必須有i>=j
????for?(int?j = 1; j <= Math.min(i, m); j++) {
??????// nums的前k-1個數(shù)被分為j-1段,然后nums（k~i）為第j段
??????// k為啥可以從0開始還沒理解 2020/07/25
??????for?(int?k = 0; k < i; k++) {
????????// 狀態(tài)轉(zhuǎn)移方程
????????dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k]));
??????}
????}
??}
??return?dp[n][m];
????}
}
LeetCode刷題實戰(zhàn)402：移掉 K 位數(shù)字
LeetCode刷題實戰(zhàn)405：數(shù)字轉(zhuǎn)換為十六進制數(shù)
LeetCode刷題實戰(zhàn)406：根據(jù)身高重建隊列