1335. Minimum Difficulty of a Job Schedule

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