2023.12.29 Today's Challenge

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

Minimum Difficulty of a Job Schedule - LeetCode

메모이제이션으로 푸는 문제

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

        if len(jobDifficulty) < d:
            return -1

        @functools.cache
        def helper(daysLeft, startJob):
            if daysLeft == 1:
                return max(jobDifficulty[startJob:])

            maxDifficulty = jobDifficulty[startJob]
            daysLeft -= 1
            stop = length - startJob - daysLeft + 1
            result = math.inf

            for i in range(1, stop):
                maxDifficulty = max(maxDifficulty, jobDifficulty[startJob + i - 1])
                result = min(result, helper(daysLeft, startJob + i) + maxDifficulty)
            
            return result

        return helper(d, 0)