Задача: 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 {
    minmaxGasDist(stations, K) {
        const N = stations.length
        const deltas = Array(N-1).fill(0).map((_, i) => stations[i+1] - stations[i])

        const dp = Array(N-1).fill(null).map(() => Array(K+1).fill(0))
        for (let i = 0; i <= K; i++) {
            dp[0][i] = deltas[0] / (i+1)
        }

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

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

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