1335. Minimum Difficulty of a Job Schedule

• 힌트를 안보고 풀어볼려고 했으나 역시 역부족이었던 문제.
• 각 날짜별로 index 구간을 나누어야 하는데 이걸 memoization으로 어떻게 표현해야 될지 몰라서 헤맸다.

• 특정 날짜에 특정 index의 작업까지 처리한 경우를 memoization하여 처리한다.

• 먼저 memoization array를 가능한 최대값으로 채운다 (로직을 단순화하기 위해).
• 또는 invalid 한 값 -1으로 채웠다가 체크하는 방법도 있긴 하다.

• 첫번째 날은 아래와 같이 계산한다.
• 첫번째 날에 첫번째 index의 작업 난이도 dp[0][0]는 단순히 전체 난이도의 첫번째 값 jobDifficulty[0]과 동일하다.
• 첫번째 날의 특정 index의 작업 난이도는 이전 index의 작업 난이도 dp[0][i - 1]와 현재 index의 작업 난이도 jobDifficulty[i] 중 큰 값이다.

• 두번째 날 부터는 아래와 같이 계산한다.
• 특정 구간 [from, to]을 잡는다 (끝점이 포함됨에 주의한다).
• 구간의 시작점 from은 해당일보다 작을 수 없다 day ≤ from < n. 왜냐하면 하루에 적어도 하나의 작업을 처리해야하기 때문이다.
• 구간의 마지막점 to은 시작점보다 작을 수 없다 from ≤ to < n.
• 특정 구간의 작업 난이도 diff를 구한다.
• 미리 계산해둘 수도 있지만 어차피 from, to 2중 루프를 돌고 있으니 메모리를 아끼는 차원에서 매번 계산한다.
• 이전 날짜 day - 1의 이전 구간 [0, from)의 작업 난이도인 dp[day - 1][from -1]와 현재 구간 [from, to]의 작업 난이도를 더한다.
• 이 결과값을 기존에 저장된 [0, to] 구간의 결과값인 dp[day][to]와 비교하여 작은 값을 다시 저장한다.

• 최종 결과값은 마지막 날, 모든 index를 다 처리한 결과인 dp[d - 1][n - 1]이 된다.

class Solution {
    final int MAX_VALUE = 300 * 1000;

    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) return -1;
        int[][] dp = new int[d][n];
        for (int i = 0; i < d; ++i) {
            Arrays.fill(dp[i], MAX_VALUE);
        }
        dp[0][0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            dp[0][i] = Math.max(dp[0][i - 1], jobDifficulty[i]);
        }
        for (int day = 1; day < d; ++day) {
            for (int from = day; from < n; ++from) {
                int diff = 0;
                for (int to = from; to < n; ++to) {
                    diff = Math.max(diff, jobDifficulty[to]);
                    int newValue = dp[day - 1][from - 1] + diff;
                    dp[day][to] = Math.min(dp[day][to], newValue);
                }
            }
        }
        return dp[d - 1][n - 1];
    }
}