Участник:Timplech/Minimum Difficulty of a Job Schedule

Материал из DISCOPAL
Перейти к: навигация, поиск

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

Python3

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jobDifficultySize = len(jobDifficulty)
        if jobDifficultySize < d:
            return -1
 
        dif_arr = [0 for _ in range(0,jobDifficultySize*d)]
        for i in range(0, jobDifficultySize):
            dif_arr[i] = jobDifficulty[jobDifficultySize-1-i]
 
        for i in range(1, jobDifficultySize):
            dif_arr[i] = max([dif_arr[i], dif_arr[i-1]])
 
        for j in range(1, d):
            for i in range(j, jobDifficultySize):
                temp_max = jobDifficulty[jobDifficultySize-1-i]
                temp_min = dif_arr[(j-1)*jobDifficultySize + i-1] + temp_max
                for k in range(i - 1, j - 1, -1):
                    temp_max = max([temp_max, jobDifficulty[jobDifficultySize-1-k]])
                    temp_min = min([temp_min, temp_max + dif_arr[((j-1)*jobDifficultySize + k-1)]])
                dif_arr[j*jobDifficultySize+i] = temp_min;
        return dif_arr[jobDifficultySize*d-1];