We define a state dp[i][j] where i is the days we have used and j is the number of finished jobs, and dp[i][j] is the minimum difficulty we need to schedule this jobs.
dp[i][j] = max([dp[i - 1][k] + max(difficulty[k:j]) for k in [0, j])
And we could add a optimize here which is to calculate the max(difficulty[k:j]) before the dp process. And the overall time complexity would be
O(d * jobs * jobs + jobs * jobs)
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
jobs = len(jobDifficulty)
# max_diff[i][j] is max(jobDifficulty[i:j + 1])
max_diff = [[0] * jobs for _ in range(jobs)]
for start in range(jobs):
m = jobDifficulty[start]
for last in range(start, jobs):
m = max(m, jobDifficulty[last])
max_diff[start][last] = m
dp = [[float('inf')] * jobs for _ in range(d)]
# Initial states for DP
for finished in range(jobs):
dp[0][finished] = max_diff[0][finished]
# DP process
for day in range(1, d):
for lastday_finished in range(day - 1, jobs):
for finished in range(lastday_finished + 1, jobs):
new_diff = max_diff[lastday_finished + 1][finished]
dp[day][finished] = min(
dp[day][finished],
dp[day - 1][lastday_finished] + new_diff
)
result = dp[d - 1][jobs - 1]
return -1 if result == float('inf') else result