Question

Code

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        J = len(jobDifficulty)
        
        if d > J:
            return -1

        memo = {}

        def dfs(i, d, cur_max):
            if i == J:
                return 0 if d == 0 else float('inf')

            if d == 0:
                return float('inf')

            if (i, d, cur_max) in memo:
                return memo[(i, d, cur_max)]

            cur_max = max(cur_max, jobDifficulty[i])

            res = min(
                dfs(i + 1, d, cur_max),
                dfs(i + 1, d - 1, -1) + cur_max
            )

            memo[(i, d, cur_max)] = res

            return res

        return dfs(0, d, -1)