Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    function minmaxGasDist($stations, $K) {
        $N = count($stations);
        $deltas = array_fill(0, $N-1, 0);
        for ($i = 0; $i < $N-1; ++$i)
            $deltas[$i] = $stations[$i+1] - $stations[$i];

        $dp = array_fill(0, $N-1, array_fill(0, $K+1, 0));
        for ($i = 0; $i <= $K; ++$i)
            $dp[0][$i] = $deltas[0] / ($i+1);

        for ($p = 1; $p < $N-1; ++$p)
            for ($k = 0; $k <= $K; ++$k) {
                $bns = 999999999;
                for ($x = 0; $x <= $k; ++$x)
                    $bns = min($bns, max($deltas[$p] / ($x+1), $dp[$p-1][$k-$x]));
                $dp[$p][$k] = $bns;
            }

        return $dp[$N-2][$K];
    }
}

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