題目網址：https://leetcode.cn/problems/split-array-largest-sum/

題意：給一非負整數 array nums 和一整數 k, 將 nums 分成 k 個非空的連續 subarray。

設計一個演算法最小化這 k 個 subarray 和的最大值（盡可能讓每個 subarray 之和都差不多）。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][k]：nums[1:i] 中 k 個 subarray 和的最大值之最小化

2. 得到轉移方程：

  • dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], sum)), 其中 1 ≤ j ≤ i
  • 最後一個元素 nums[i], 必定是在當前最後一個連續 subarray 中, 因此要考慮這個區間的起始元素 j 會在哪裡 ➔ 故從 i 往前倒推

3. 初始化：

  • dp[0][0]：空 array 可分割成 0 個 subarray, 且 subarray 最大和最小化之值為 0
    ➔ dp[0][0] = 0
  • dp[i][0]：非空 array 不可能分割成 0 個 subarray, 故用 INT_MAX / 2 代表不可能。由於題目要求最小值, 故初始值要設大, 但設 INT_MAX 可能會導致後續計算 overflow, 故設 INT_MAX / 2
    ➔ dp[i][0] = INT_MIN / 2, 其中 1 ≤ i ≤ n
  • dp[0][k]：空 array 不可能分成 k 個 subarray, 故用 INT_MAX / 2 代表不可能
    ➔ dp[0][k] = INT_MIN / 2, 其中 1 ≤ k ≤ k_
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        const int n = nums.size();
        int k_ = k;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX / 2));

        nums.emplace(nums.begin(), 0);
        dp[0][0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= min(i, k_); ++k) {
                int sum = 0;
                for (int j = i; j >= k; --j) { // 從最後一個元素 i 往前倒推
                    sum += nums[j];
                    dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], sum));
                }
            }
        }

        return dp[n][k];
    }
};
  • time：$O(n^2 \cdot k)$ ➔ for loop 中 i、k、j 所需的時間分別為 $O(n)$、$O(k)$、$O(n)$
  • space：$O(n \cdot k)$ ➔ dp