1335. Minimum Difficulty of a Job Schedule

Python

Top Down DP

• Time: O(N**2 * d)

• Space: O(N**2 * d)

• 預先做prefix sum拿出每個index往右看最大的值，用以決定在index時的difficulty

• DP要跑所有可能，但只用一個變數(diff)存，意義上是2D DP的降維打擊

from math import inf

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        length = len(jobDifficulty)

        if length < d:
            return -1

        max_remaing = jobDifficulty[:]
        for i in range(length-2, -1, -1):
            max_remaing[i] = max(max_remaing[i], max_remaing[i + 1])

        @cache
        def dp(i, remains):
            if remains == 1:
                return max_remaing[i]

            res = inf
            diff = 0

            for j in range(i, length-remains+1):
                diff = max(diff, jobDifficulty[j])
                res = min(res, diff + dp(j+1, remains-1))

            return res

        return dp(0, d)