algorithm - 动态规划 : Find possible ways to reach destination

Question

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

---

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

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

史蒂文可以从多少个城市开始他的汽车，这样他就可以环游世界并到达他开始的同一个城市？

注意

油箱最初是空的。

输入格式 第一行包含两个整数(以空格分隔):城市编号 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
说明

史蒂文从 0 号城市出发，为他的汽车加满 3 加仑燃油，并使用 2 加仑燃油前往城市 1。他的油箱现在有 1 加仑燃油。 在城市 1 加油 1 加仑燃料后，他使用 2 加仑燃料前往城市 2。他的油箱现在是空的。 在城市 2 加油 2 加仑燃料后，他又使用 2 加仑燃料返回城市 0。

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

但是，史蒂文不能从城市 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;
}