LC.P1335[工作计划的最低难度]

方法一：动态规划+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int[] jobDifficulty;
    int[][] cache;

    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) return -1;
        this.jobDifficulty = jobDifficulty;
        this.cache = new int[d][n];
        for (int i = 0; i < d; ++i) {
            Arrays.fill(cache[i], -1);
        }
        return dfs(d - 1, n - 1);
    }

    /**
     * dfs(i,j)表示用i+1天完成0~j天的工作
     */
    private int dfs(int i, int j) {
        if (cache[i][j] != -1) return cache[i][j];
        // 只有一天，必须完成所有工作
        if (i == 0) {
            int max = 0;
            for (int k = 0; k <= j; ++k) {
                max = Math.max(max, jobDifficulty[k]);
            }
            return cache[i][j] = max;
        }
        int max = 0, ans = Integer.MAX_VALUE;
        for (int k = j; k >= i; --k) {
            max = Math.max(max, jobDifficulty[k]);
            ans = Math.min(ans, dfs(i - 1, k - 1) + max);
        }
        return cache[i][j] = ans;
    }
}
  • 时间复杂度：动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题中状态个数为$O(nd)$，单个状态的计算时间为$O(n)$，因此时间复杂度为$O(n^2d)$
  • 空间复杂度：$O(nd)$

方法二：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) return -1;
        int[][] f = new int[d][n];
        f[0][0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            f[0][i] = Math.max(f[0][i - 1], jobDifficulty[i]);
        }
        for (int i = 1; i < d; ++i) {
            for (int j = n - 1; j >= i; --j) {
                f[i][j] = Integer.MAX_VALUE;
                int max = 0;
                for (int k = j; k >= i; --k) {
                    max = Math.max(max, jobDifficulty[k]);
                    f[i][j] = Math.min(f[i][j], f[i - 1][k - 1] + max);
                }
            }
        }
        return f[d - 1][n - 1];
    }
}
  • 时间复杂度：动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题中状态个数为$O(nd)$，单个状态的计算时间为$O(n)$，因此时间复杂度为$O(n^2d)$
  • 空间复杂度：$O(nd)$