Leetcode 1457 Solution

This article provides solution to leetcode question 1457 (minimum-difficulty-of-a-job-schedule)
Categories:
Tags:
Access this page by simply typing in "lcs 1457" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule

Solution

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

        memo = {}
        def dfs(i, d):
            nonlocal jobDifficulty

            if i == len(jobDifficulty) and d == 0:
                return 0

            if i == len(jobDifficulty) or d == 0:
                return -1

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

            day_difficulty = 0
            schedule_difficulty = sys.maxsize

            for j in range(i, len(jobDifficulty)):
                day_difficulty = max(day_difficulty, jobDifficulty[j])

                child_difficulty = dfs(j + 1, d - 1)
                if child_difficulty == -1:
                    continue

                schedule_difficulty = min(schedule_difficulty, child_difficulty + day_difficulty)

            memo[key] = schedule_difficulty if schedule_difficulty != sys.maxsize else -1
            return memo[key]

        return dfs(0, d)