# 1335. Minimum Difficulty of a Job Schedule
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
## 思路
## Code
java

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if(n<d) return -1;
        int[] arr = new int[n+1];
        for(int i=0; i<n; i++) arr[i+1] = jobDifficulty[i];
        int[][] dp = new int[n+1][d+1];
        for(int i=0; i<=n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int k=1; k<=Math.min(i,d); k++){
                int max = arr[i];
                for(int j=i; j>=k; j--){
                    max = Math.max(max, arr[j]);
                    dp[i][k] = Math.min(dp[i][k], dp[j-1][k-1]+max);
                }
            }
        }
        return dp[n][d];
    }
}

c++

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if(n<d) return -1;
        int[] arr = new int[n+1];
        for(int i=0; i<n; i++) arr[i+1] = jobDifficulty[i];
        int[][] dp = new int[n+1][d+1];
        for(int i=0; i<=n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int k=1; k<=Math.min(i,d); k++){
                int max = arr[i];
                for(int j=i; j>=k; j--){
                    max = Math.max(max, arr[j]);
                    dp[i][k] = Math.min(dp[i][k], dp[j-1][k-1]+max);
                }
            }
        }
        return dp[n][d];
    }
}