algorithm - 货车上路及加油站问题的动态规划算法

Question

一辆卡车行驶 1 个单位的距离需要消耗 1 个单位的燃料。卡车必须到达沿路 L 个单位距离的城镇，并且在起点卡车的油箱中有 P 个单位的燃料(均为值被给出为 (L,P) 对)。油箱是无限的，所以卡车总是可以储存更多的燃料。沿途可能的加油站数量以整数对(a,b)给出，其中a是城镇与加油站之间的距离，b为本次加油站可提供的加油单位数。

我们的目标是在前往城镇的路上尽可能少地停靠。该算法必须返回完成行程所需的最少停靠站数。

我想出了如何使用贪心算法解决这个问题，使用优先队列，但我正在努力寻找一个动态的方法来解决这个问题。我知道有一个，但我无法弄清楚。我会很感激任何提示。

Answer 1

从 https://leetcode.com/problems/minimum-number-of-refueling-stops/solution/ 复制的想法,

让我们确定 dp[i]，我们可以到达使用第 i 个加油站的最远位置。这是因为我们想要 dp[i] >= target 的最小 i。

算法

让我们更新 dp，因为我们按顺序考虑每个站点。在没有加油站的情况下，显然我们可以获得 0 次加油站的 startFuel 的最大距离。

现在让我们看看更新步骤。当添加一个站点 station[i] = (location, capacity) 时，任何时候我们可以通过 t 次加油站到达该站点，我们现在可以通过 t+1 次加油站进一步达到容量。

例如，如果我们可以通过 1 次加油站到达 15 的距离，现在我们在位置 10 处添加了一个加注 30 升燃油的加油站，那么我们有可能通过 2 次加油站到达 45 的距离。

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int N = stations.length;
    long[] dp = new long[N + 1];
    dp[0] = startFuel;
    for (int i = 0; i < N; ++i)
        for (int t = i; t >= 0; --t)
            if (dp[t] >= stations[i][0])
                dp[t+1] = Math.max(dp[t+1], dp[t] + (long) stations[i][1]);

    for (int i = 0; i <= N; ++i)
        if (dp[i] >= target) return i;
    return -1;
}

复杂度分析

时间复杂度:O(N^2)，其中 N 是站点的长度。

空间复杂度:O(N)，dp 使用的空间。