# 1335. Minimum Difficulty of a Job Schedule



````java
```java
class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) {
            return -1;
        }
        Integer[][] memo = new Integer[n][d+1]; // d only ha 1 2 3..
        return dfs(jobDifficulty, 0, d, memo);
    }
    private int dfs(int[] jobDifficulty, int index, int d, Integer[][] memo) {
        int n = jobDifficulty.length;
        if (d == 1) {
            int max = 0;
            for (int i = index; i < n; i++) {
                max = Math.max(max, jobDifficulty[i]);
            }
            return max;
        }
        if (memo[index][d] != null) {
            return memo[index][d];
        }
        int result = Integer.MAX_VALUE;
        int max = 0;
        for (int i = index; i <= n - d; i++) {
            max = Math.max(max, jobDifficulty[i]);
            result = Math.min(result, max + dfs(jobDifficulty, i+1, d-1, memo));
        }
        return memo[index][d] = result;
    }
}

/***
like a group problem?
get Max in each state

    dp(0,3).   (range: 7 - 3 = 4 times)
     /
dp(1,2). dp(2,2) dp(3,2)               dp(4,2)        xxx(5,2) ... at least one job for each day
   /          \      \                  \
  /            \     dp(4,1) dp(5,1)     \
 /           dp(3,1) dp(4,1) dp(5,1)      \ 
/                                         dp(5,1)
dp(2,1) dp(3,1) dp(4,1) dp(5,1)

dp(0,3) = max + min(dp(1,2), dp(2,2) dp(3,2))

Time complexity: O(n^2⋅d)
since there are O(n⋅d) possible states, and we need O(n)time to calculate the result for each state (for loop).

Space complexity: O(n⋅d) space is required to memoize all O(n⋅d) states.
 */
```
````
