题目描述

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。

你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1。

样例

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6。
第二天，您可以完成最后一项工作，总难度 = 1。
计划表的难度 = 6 + 1 = 7 

输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。

输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3。

输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15

输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843

限制

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

算法

(动态规划) $O(n^2d)$

1. 状态 $f(i, j)$ 表示前 $i$ 项任务，用了 $j$ 天完成的最小难度，$i$ 和 $j$ 的下标从 1 开始。
2. 初始时，$f(i, j) = +\infty$，但 $f(0, 0) = 0$。
3. 转移时，从 $0$ 到 $i - 1$ 枚举 $k$，令 [k + 1, i] 为第 $j$ 天的任务，则有 $f(i, j) = \min(f(i, j), f(k, j - 1) + \max(diff(k + 1, i)))$。其中 $diff(i, j)$ 为 [i, j] 任务难度的最大值。
4. 最终答案为 $f(n, d)$。

时间复杂度

• 预处理 $diff$ 数组需要 $O(n^2)$ 的时间。
• 动态规划状态数为 $O(nd)$，转移需要 $O(n)$ 的时间。
• 故总时间复杂度为 $O(n^2d)$。

空间复杂度

• 需要 $O(n^2)$ 的空间存储 $diff$ 数组，以及 $O(nd)$ 的空间存储状态。
• 故总空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        const int INF = 1000000000;
        vector<vector<int>> f(n + 1, vector<int>(d + 1, INF));
        vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; i++) {
            diff[i][i] = jobDifficulty[i - 1];
            for (int j = i + 1; j <= n; j++)
                diff[i][j] = max(diff[i][j - 1], jobDifficulty[j - 1]);
        }

        f[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= min(d, i); j++)
                for (int k = 0; k < i; k++)
                    f[i][j] = min(f[i][j], f[k][j - 1] + diff[k + 1][i]);

        if (f[n][d] == INF)
            f[n][d] = -1;

        return f[n][d];
    }
};