道路和燃油停站问题的动态规划算法

Question

一辆卡车在行驶1单位距离时燃烧1单位燃料。卡车必须到达城镇，该镇位于公路沿线的L单元，而在该卡车的起始点，油箱中有P单位的燃料(这两个值都给出为(L，P)对)。油箱是无限的，所以卡车总是可以储存更多的燃料。道路上的一些可能的燃料站是以整数(a，b)的形式给出的，其中a是该镇与燃料站之间的距离，b是这个燃料站可以提供的燃料单位数。

我们的目标是在去城镇的路上尽量少停留。该算法必须返回旅行所需的最小停止数。

我想出了如何用一个贪婪的算法来解决这个问题，使用优先级队列，但是我很难找到一个动态的方法来解决这个问题。我知道有一个，但我想不出来。任何提示我都会感激的。

Answer 1

从https://leetcode.com/problems/minimum-number-of-refueling-stops/solution/抄袭的想法，

让我们确定dpi，我们可以使用我加油站的最远位置。这是由这样一个事实所驱动的:我们想要最小的i，其中dpi是>=的目标。

算法

让我们在考虑每个站点的顺序时更新dp。没有站，显然我们可以得到最大距离的startFuel与0加油停止。

现在让我们来看看更新步骤。当添加站点i=(位置，容量)时，任何时候我们都可以使用t加油站到达这个站点，现在我们可以使用t+1加油站进一步达到容量。

例如，如果我们可以达到15的距离，一个加油停止，现在我们增加了一个站在位置10，有30升的燃料，那么我们有可能达到45的距离，有2个加油站。

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使用的空间。