2023.12.29 Today's Challenge

fabichoi 2023. 12. 29. 23:45

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

Minimum Difficulty of a Job Schedule - LeetCode

Can you solve this real interview question? Minimum Difficulty of a Job Schedule - You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i). You have to finish at lea

leetcode.com

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

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)