題目網址：https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/

題意：你需要制定一份 d 天的工作計劃表, 每個工作之間是互相依賴的, 要想執行第 i 項工作, 則必須完成前 j 項工作（0 ≤ j < i）。

每天至少需要完成一項任務, 工作計劃的總難度是這 d 天每一天的難度之和, 而一天的工作難度是當天應該完成工作的最大難度。

給一整數 array jobDifficulty 和一整數 d, 分別代表工作難度和需要計劃的天數, 其中第 i 項工作的難度是 jobDifficulty[i]。

返回整個工作計劃的最小難度。若無法制定工作計劃, 則返回 -1。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 jobDifficulty 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][k]：jobDifficulty[1:i] 分割成 k 個 subarray 的最小難度和

2. 得到轉移方程：

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

3. 初始化：

  • dp[0][0]：空 array 分割成 0 個 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 minDifficulty(vector<int>& jobDifficulty, int d) {
        const int n = jobDifficulty.size();
        vector<vector<int>> dp(n + 1, vector<int>(d + 1, INT_MAX / 2));

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

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= min(i, d); ++k) {
                const int curMax = jobDifficulty[i];
                for (int j = i; j >= k; --j) {
                    curMax = max(curMax, jobDifficulty[j]);
                    dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + curMax);
                }
            }
        }

        return (dp[n][d] >= INT_MAX / 2) ? -1 : dp[n][d];
    }
};
  • time：$O(n^2 \cdot k)$ ➔ for loop 中 i、k、j 所需的時間分別為 $O(n)$、$O(k)$、$O(n)$
  • space：$O(n \cdot k)$ ➔ dp