# [1335. Minimum Difficulty of a Job Schedule](https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/?envType=daily-question&envId=2023-12-29)
###### tags: `Leetcode` `Hard` `DP`
這題剛開始很難，但是看到[這個人](https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/solutions/944828/short-dp-solution-with-highly-detailed-step-by-step-explanation/?envType=daily-question&envId=2023-12-29)解釋，我覺得大概了解了，留個紀錄。
////>ㄇ<////

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n=jobDifficulty.size(),inf=1e9;
        if(n<d) return -1;
        vector<int> dp(n+1,1e9);
        dp[n]=0;
        for(int day=1;day<=d;day++){
            // 可以想成，對一個subarray做切割並且找裡面最大的值
            // ex : job=[6,5,4,3,2,1] d=1 , start=0 , end = 6 -> 找出 job[start:end] 的最大值
            // dp[i] 第d個切法裡面的每個subarray裡面最大值的總和
            // ex : job=[6,5,4,3,2,1] d=1 -> dp=[6,6,6,6,6,1,0] 
            // d=2 -> dp=[7,6,5,4,3,2,1]  
            // 在d+1時候 dp[end+1]從第(end+1)th的值 ~ (n-1)th的值 中第d個切法裡面的每個subarray裡面最大值的總和
            // 所以再用d=3的時候 就可以變成這樣 dp[start]=[start:end][maxvalue with cut number 2]
            for(int start=0;start<=n-day;start++){
                int maxd=0;
                dp[start]=inf;
                for(int end=start;end<=n-day;end++){
                    maxd=max(maxd,jobDifficulty[end]);
                    dp[start]=min(dp[start],maxd+dp[end+1]);
                }
            }    
        }
        return dp[0];
    }
};