动态规划:寻找到达目的地的可能路径

Question

我正在尝试解决这个问题，O(N^2)的解决方案很简单，O(N)是可能的，但我想不出怎么做。问题是:

---

Steven的世界里有N个城市和N条定向道路。这些城市的编号从0到N - 1。史蒂文可以从城市i到城市(i + 1) % N， (0-> 1 -> 2 -> ....-> N - 1 -> 0).

史蒂文想开车环游世界。他汽车油箱的容量是C加仑。他可以在城市i的起点使用[i]加仑的汽油，而汽车从城市i行驶到(i + 1) % n需要b[i]加仑的汽油

Steven可以从几个城市出发，这样他就可以环游世界并到达他出发的同一个城市?

注意

油箱初始为空。

输入格式第一行包含两个整数(以空格分隔):城市号N和容量C。第二行包含N个空格分隔的整数:a[0]， a[1]，…，a[N - 1]。第三行包含N个空格分隔的整数:b[0]， b[1]，…，b[N - 1]。

输出格式可以选择作为起始城市的城市数目。

示例输入

3

3
3 1 2
2 2 2
样例输出

2
解释

Steven从城市0出发，给他的车加满3加仑的燃料，然后用2加仑的燃料到达城市1。他的油箱现在有1加仑的燃料。在城市1加满1加仑的燃料后，他再用2加仑的燃料前往城市2。他的油箱现在空了。在城市2加满2加仑燃料后，他又用2加仑燃料回到城市0。

这是第二个可能的解决方案。史蒂文从2号城市出发，给他的车加满2加仑，然后前往0号城市。在从城市0加满3加仑燃料后，他又前往城市1，并消耗了2加仑燃料。他的油箱里现在有一加仑的燃料。然后他可以在城市1加满1加仑的燃料，并将他的汽车燃料增加到2加仑，然后前往城市2。

然而，Steven不能从城市1出发，因为他只有1加仑的燃料，但是到城市2需要2加仑的燃料。

因此答案是2。

---

现在我知道这个算法可以在O(N)时间复杂度内解决，这是我无法做到的，我猜它可以用动态规划来解决，请帮助我得到一个线索，它是如何分解成子问题的。

Answer 1

我已经制作了一个应该解决问题的算法，它为您的案例输出2，但必须在其他测试用例上进行测试。我不确定它是否正确。我的主要想法是，如果你能从一个点开始迭代，你就能得到你想要的次数，反之亦然。如果你不能制造一个以上，那你就连一个也造不出来。

#include <algorithm>
#include <iostream>
using namespace std;
#define PROB_SIZE 3
int n = PROB_SIZE, c = 3;
int a[PROB_SIZE] = {3, 1, 2}; // available
int b[PROB_SIZE] = {2, 2, 2}; // used
int d[PROB_SIZE];
int dmin[PROB_SIZE];
int main()
{
    //The fuel used in the trip to next node (amount put in minus the amount consumed in one trip).
    for (int i = 0; i < n; i++) {
        d[i] = a[i] - b[i];
    }
    //The fuel that i need to start a trip in this point and reach point 0.
    dmin[n - 1] = d[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        dmin[i] = min(d[i], d[i] + dmin[i + 1]);
    }
    //The second loop to be sure i cover a whole loop from any point.
    dmin[n - 1] = min(d[n - 1], d[n - 1] + dmin[0]);
    for (int i = n - 2; i >= 0; i--) {
        dmin[i] = min(d[i], d[i] + dmin[i + 1]);
    }
    //If for any point i need to have more fuel than i can carry then the trip is impossible for all points.
    for (int i = 0; i < n; i++) {
        if ((-dmin[i] + a[i]) > c) {
            cout << 0 << endl;
            return 0;
        }
    }
    int cnt = 0;
    //Any point that i need to have 0 fuel to reach point 0 making at least one round trip is a good starting point.
    for (int i = 0; i < n; i++) {
        if (dmin[i] >= 0) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

Answer 2

首先，我想指出，这个问题是逐字逐句地从HackerRank上的一个练习中提取出来的。

这是一个算法的草图，该算法已被确认在O(N)时间内通过了该站点上针对该特定问题的所有测试用例。

对于所有部分"行程"从0开始，到1结束，为0

1. 为了成功地从0到i，我们需要从0城市开始旅行的最小汽油量是多少?

2. 从这个最小量开始(假设部分旅行是可能的)当我们进入城市i时，我们将有多少汽油?

3. 在这样的旅行中，你油箱里最大的汽油量是多少?

我们需要#3的原因是因为有限的油箱容量有时使我们无法获取"气体剖面";只是"把所有的东西都搬上去"。知道在某段旅程中我们离天花板有多近，就能准确地告诉我们我们能"向上移动"多少。在我们撞到天花板之前。(这听起来含糊不清，但我们应该仔细考虑这一点。)

一旦你有了这三个0 <我&><我&>

使用一些稍微聪明的动态规划，可以在每个城市的O(1)时间内计算出所有这六个价值数字，一旦你拥有了所有城市的所有价值数字，就需要O(1)时间来检查一个城市是否可以完全环绕。

下面是上述想法的python实现:

def travelAroundTheWorld(a, b, c):
    a = [min(i,c) for i in a]
    if max(b) > c:
        return 0
    min_req, max_reached, remaining_cap,Min_req, Max_reached, Remaining_cap= ([0]*(len(a)+1) for _ in range(6))
    for i in range(1,len(a)):
        if b[i-1] > a[i-1]+remaining_cap[i-1]:
            if c-max_reached[i-1] < b[i-1]-remaining_cap[i-1]-a[i-1]:
                return 0
            min_req[i] = min_req[i-1] + b[i-1]-remaining_cap[i-1]-a[i-1]
            remaining_cap[i] = 0
            max_reached[i] = max(max_reached[i-1]+b[i-1]-remaining_cap[i-1]-a[i-1],b[i-1])
        else:
            min_req[i] = min_req[i-1]
            remaining_cap[i] = min(remaining_cap[i-1]+a[i-1], c) - b[i-1]
            max_reached[i] = max(max_reached[i-1],min(remaining_cap[i-1]+a[i-1], c))
    for i in range(len(a)-1,0,-1):
        if Min_req[i+1] + b[i] > c:
            return 0
        if b[i] > a[i]:
            Min_req[i] = Min_req[i+1] + b[i]-a[i]
            Remaining_cap[i] = Remaining_cap[i+1]
            Max_reached[i] = max(Max_reached[i+1], a[i]+Min_req[i])
        elif a[i]-b[i]>Min_req[i+1]:
            Min_req[i] = 0
            Remaining_cap[i] = Remaining_cap[i+1] + min(c-Max_reached[i+1], a[i]-b[i]-Min_req[i+1])
            Max_reached[i] = max(a[i], min(c, Max_reached[i+1]+a[i]-b[i]-Min_req[i+1]))
        else:
            Min_req[i] = Min_req[i+1] + b[i]-a[i]
            Remaining_cap[i] = Remaining_cap[i+1]
            Max_reached[i] = max(Max_reached[i+1], Min_req[i]+a[i])
    ans = 0
    if min_req[1] == 0 and remaining_cap[1] >= Min_req[1]:
        ans = 1
    for i in range(1,len(a)):
        if Min_req[i] == 0 and Remaining_cap[i] >= min_req[i]:
            ans += 1
    return ans

Answer 3

当您试图找出是否可以从城市i返回到城市i时，您需要收集以前城市的信息。我将创建一个包含信息的堆栈，你可以从x城市开始，到达y城市，油箱里有z燃料。

当你检查城市j时，你发现你可以在j的油箱里放X油，开车到j+1需要Y油。如果X>= Y，则将该信息放到堆栈中。否则，弹出堆栈顶部。这里的信息会告诉你，你可以从x点开始到达j点，油箱里有z燃料。从x点开始，你会让j的最小值(z + x, C)留在容器里。如果这样就足够了，将信息推回堆栈。如果不是，从堆栈中弹出下一个项目。如果堆栈是空的，就没有办法到达j+1。

现在你需要弄清楚如何结束搜索，并证明只有O (N)个操作。

Answer 4

更简单的方法:你有一个城市列表，你一个接一个地删除那些你不能开始的城市。

你寻找第一个没有足够燃料到达城市i+1的城市i。如果没有这样的城市，你可以从任何地方开始。因为你不能从i到i+1，所以你将它从城市列表中删除，但你需要将它与前一个城市结合起来。如果前一个城市有x燃料，需要y, x>= y，而第i个城市有x燃料，需要y，你做以下操作:

1. 将X替换为min (X, C - (X - y))(因为额外的燃料不能使用)
2. 从y和X中减去min (y, X)(因为这是你可以重新填充的)
3. 将x替换为min (C, x + x)， y替换为y + y

此时，再次检查前一个城市。当你可以从一个城市到另一个城市时，你就完成了。你可能会在一个城市无法到达下一个城市;在这种情况下，你失败了。

Answer 5

static int n = 3;
static int c = 3;
static int a[] = {3, 1, 2}; 
static int b[] = {2, 2, 2}; 
static int currentCity;
public static void main(String[] args) {
    List<String> citi = new ArrayList<String>();
    //try one by one
    for(int i = 0; i < n; i ++){
        currentCity = i;
        if(!startFrom(i, 0))
            continue;
        citi.add("citi" + i);
    }
    for (String s: citi)
        System.out.println(s);
}
public static boolean startFrom(int i, int left){
    int tankVal = (a[i] + left) > c ? c : (a[i] + left);
    if(b[i] > tankVal)
        return false;
    left = tankVal - b[i];
    int next = (i + 1) % n;
    if(next == currentCity)
        return true;
    return startFrom(next, left);
}