1335. Minimum Difficulty of a Job Schedule
https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
solution
给定的数组 jobDifficulty 分为d个子数组,然后将每个子数组中的最大值加起来,使得这个总和最小
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if d > n:
return -1
# dp[i][k] := the minimum difficulty to schedule the first i jobs in k days
dp = [[math.inf] * (d + 1) for _ in range(n + 1)]
dp[0][0] = 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
maxDifficulty = max(maxDifficulty, jobDifficulty[j]) # 0-based
dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxDifficulty)
return dp[n][d]
时间复杂度:O() 空间复杂度:O()
Last updated