# 1335. Minimum Difficulty of a Job Schedule    • Time: $O(n^2d)$
• Space: $O(nd)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int minDifficulty(vector& jobDifficulty, int d) { const int n = jobDifficulty.size(); if (n < d) return -1; // dp[i][k] := min difficulty to schedule the first i jobs in k days vector> dp(n + 1, vector(d + 1, INT_MAX / 2)); dp = 0; for (int i = 1; i <= n; ++i) for (int k = 1; k <= d; ++k) { int maxDifficulty = 0; // Max(job[j + 1..i]) for (int j = i - 1; j >= k - 1; --j) { // 1-based maxDifficulty = max(maxDifficulty, jobDifficulty[j]); // 0-based dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxDifficulty); } } return dp[n][d]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int minDifficulty(int[] jobDifficulty, int d) { final int n = jobDifficulty.length; if (n < d) return -1; // dp[i][k] := min difficulty to schedule the first i jobs in k days int[][] dp = new int[n + 1][d + 1]; Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE / 2)); dp = 0; for (int i = 1; i <= n; ++i) for (int k = 1; k <= d; ++k) { int maxDifficulty = 0; // Max(job[j + 1..i]) for (int j = i - 1; j >= k - 1; --j) { // 1-based maxDifficulty = Math.max(maxDifficulty, jobDifficulty[j]); // 0-based dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + maxDifficulty); } } return dp[n][d]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: n = len(jobDifficulty) if d > n: return -1 # dp[i][k] := min difficulty to schedule the first i jobs in k days dp = [[math.inf] * (d + 1) for _ in range(n + 1)] dp = 0 for i in range(1, n + 1): for k in range(1, d + 1): maxDifficulty = 0 # Max(job[j + 1..i]) for j in range(i - 1, k - 2, -1): # 1-based # 0-based maxDifficulty = max(maxDifficulty, jobDifficulty[j]) dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxDifficulty) return dp[n][d]