774. Minimize Max Distance to Gas Station

public class Solution {
    public double MinmaxGasDist(int[] stations, int K) {
        int N = stations.Length;
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];
        double[][] dp = new double[N-1][];
        for (int i = 0; i < N-1; ++i)
            dp[i] = new double[K+1];
        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);
        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = double.MaxValue;
                for (int 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];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double MinmaxGasDist(vector<int>& stations, int K) {
        int N = stations.size();
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];
        double[][] dp = new double[N-1][];
        for (int i = 0; i < N-1; ++i)
            dp[i] = new double[K+1];
        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);
        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = double.MaxValue;
                for (int 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];
    }
}

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        int N = stations.length;
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];

        double[][] dp = new double[N-1][K+1];
        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);

        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = Double.MAX_VALUE;
                for (int 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];
    }
}

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]
    }
}

class Solution:
    def minmaxGasDist(self, stations: List[int], K: int) -> float:
        N = len(stations)
        deltas = [0] * (N-1)
        for i in range(N-1):
            deltas[i] = stations[i+1] - stations[i]

        dp = [[0] * (K+1) for _ in range(N-1)]
        for i in range(K+1):
            dp[0][i] = deltas[0] / (i+1)

        for p in range(1, N-1):
            for k in range(K+1):
                bns = float('inf')
                for x in range(k+1):
                    bns = min(bns, max(deltas[p] / (x+1), dp[p-1][k-x]))
                dp[p][k] = bns

        return dp[N-2][K]

func minmaxGasDist(stations []int, K int) float64 {
    N := len(stations)
    deltas := make([]float64, N-1)
    for i := 0; i < N-1; i++ {
        deltas[i] = float64(stations[i+1] - stations[i])
    }

    dp := make([][]float64, N-1)
    for i := range dp {
        dp[i] = make([]float64, K+1)
    }
    for i := 0; i <= K; i++ {
        dp[0][i] = deltas[0] / float64(i+1)
    }

    for p := 1; p < N-1; p++ {
        for k := 0; k <= K; k++ {
            bns := 1e9
            for x := 0; x <= k; x++ {
                bns = math.Min(bns, math.Max(deltas[p] / float64(x+1), dp[p-1][k-x]))
            }
            dp[p][k] = bns
        }
    }

    return dp[N-2][K]
}

Algorithm

Пусть 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.