Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard

Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).

Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.

Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].

Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.

Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

👨‍💻 Алгоритм:

1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.

2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.

3⃣Базовый случай:
Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач.

😎 Решение:

class Solution {
    function minDifficulty($jobDifficulty, $d) {
        $n = count($jobDifficulty);
        if ($n < $d) return -1;
        
        $mem = array_fill(0, $n, array_fill(0, $d + 1, -1));
        
        function minDiff($i, $daysRemaining, $jobDifficulty, &$mem) {
            if ($mem[$i][$daysRemaining] != -1) {
                return $mem[$i][$daysRemaining];
            }
            
            if ($daysRemaining == 1) {
                return max(array_slice($jobDifficulty, $i));
            }
            
            $res = PHP_INT_MAX;
            $dailyMaxJobDiff = 0;
            
            for ($j = $i; $j < count($jobDifficulty) - $daysRemaining + 1; $j++) {
                $dailyMaxJobDiff = max($dailyMaxJobDiff, $jobDifficulty[$j]);
                $res = min($res, $dailyMaxJobDiff + minDiff($j + 1, $daysRemaining - 1, $jobDifficulty, $mem));
            }
            
            $mem[$i][$daysRemaining] = $res;
            return $res;
        }
        
        return minDiff(0, $d, $jobDifficulty, $mem);
    }
}

Ставь 👍 и забирай 📚 Базу знаний