1335. Minimum Difficulty of a Job Schedule 풀이 python

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

Minimum Difficulty of a Job Schedule - LeetCode

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

        dp = [[-1] * (d+1) for _ in range(N+1)]

        INF = 987654321

        def dfs(si, d):
            if dp[si][d] != -1:
                return dp[si][d]

            if d == 1:
                return max(jobDifficulty[si:])
            
            dp[si][d] = INF

            for i in range(si, (N - d) + 1):
                dp[si][d] = min(dp[si][d], max(jobDifficulty[si:i+1]) + dfs(i+1, d-1))
        

            return dp[si][d]


        return dfs(0, d)

 

 

다른 사람들 풀이를 보는데 뭔 알아보지도 못하는것만 잔뜩 있어서 직접 올린다.

부분 문제로 바꿀 수 있으면 dp를 사용할 수 있다. 이 풀이는 dfs로 탑 다운 방식으로 풀기에 부분문제가 앞이 아닌 뒤에서부터 조금씩 만들어져서 원래 문제까지 확장한다.

 

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/solutions/4478864/python-code-that-easy-to-read/

python code that easy to read - undefined - LeetCode