题目描述

给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量。

每一步中，如果你在城市 i，你可以选择任意一个城市 j，满足 j != i 且 0 <= j < locations.length，并移动到城市 j。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。

请注意，fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish）。

请你返回从 start 到 finish 所有可能路径的数目。

由于答案可能很大，请将它对 10^9 + 7 取余后返回。

样例

输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出：5
解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5

输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2。
因为最短路径需要 4 单位的汽油。

输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
输出：2
解释：总共有两条可行路径，0 和 0 -> 1 -> 0。

输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
输出：615088286
解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286。

限制

• 2 <= locations.length <= 100
• 1 <= locations[i] <= 10^9
• 所有 locations 中的整数 互不相同。
• 0 <= start, finish < locations.length
• 1 <= fuel <= 200

算法

(动态规划) $O(fuel \times n^2)$

1. 设状态 $f(i, j)$ 表示目前有 $i$ 的汽油，在城市 $j$ 时到达终点的方案数。
2. 初始时，对于 $0 \le i \le fuel$，有 $f(i, finish) = 1$，其余为 0。
3. 转移时，对于 $f(i, j)$ 考虑下一个城市 $k$，满足 $j \neq k$，且花费的油量 $cost$ 小于等于 $i$，转移 $f(i, j) = f(i, j) + f(i-cost, k)$。
4. 最终答案为 $f(fuel, start)$。

时间复杂度

• 状态数为 $O(fuel \times n)$，每次转移有 $n$ 种，故总时间复杂度为 $O(fuel \times n^2)$。

空间复杂度

• 需要 $O(fuel \times n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        const int mod = 1000000007;
        vector<vector<int>> f(fuel+1, vector<int>(n, 0));

        for (int i = 0; i <= fuel; i++)
            f[i][finish] = 1;

        for (int i = 1; i <= fuel; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++) {
                    int cost = abs(locations[j] - locations[k]);
                    if (j != k && i >= cost)
                        f[i][j] = (f[i][j] + f[i-cost][k]) % mod;
                }

        return f[fuel][start];
    }
};