本文共 1397 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要制定一个d天的工作计划，每天至少完成一项任务，并且工作之间存在依赖关系。我们的目标是找到整个计划的最小总难度，如果无法完成任务则返回-1。

方法思路

我们可以使用动态规划来解决这个问题。定义一个二维数组dp，其中dp[i][j]表示在第i天完成j项工作的最小总难度。我们需要填充这个二维数组，找到最优的工作安排方式。

解决代码

from typing import List
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        
        dp = [[-1] * (n + 1) for _ in range(d + 1)]
        dp[1][1] = jobDifficulty[0]
        for i in range(2, n + 1):
            dp[1][i] = max(dp[1][i - 1], jobDifficulty[i - 1])
        
        for i in range(2, d + 1):
            for j in range(i, n + 1):
                dp[i][j] = dp[i - 1][j - 1] + jobDifficulty[j - 1]
                for k in range(j - 2, i - 2, -1):
                    current_max = max(jobDifficulty[k], jobDifficulty[j - 1])
                    if dp[i - 1][k] + current_max < dp[i][j]:
                        dp[i][j] = dp[i - 1][k] + current_max
        
        return dp[d][n] if dp[d][n] != -1 else -1

代码解释

通过这种方法，我们可以高效地找到完成任务的最小总难度，确保每天至少完成一项任务并满足依赖关系。