C++刷LeetCode（1575. 统计所有可行路径）【动态规划】
题目描述：给你一个 互不相同 的整数数组，其中 locations 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations - locations|，|x| 表示 x 的绝对值。
请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
请你返回从 start 到 finish 所有可能路径的数目。
由于答案可能很大， 请将它对 10^9 + 7 取余后返回。
示例 1：
输入：locations = , start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3
示例 2：
输入：locations = , 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
示例 3：
输入：locations = , start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
示例 4 ：
输入：locations = , start = 0, finish = 0, fuel = 3
输出：2
解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。
示例 5：
输入：locations = , start = 0, finish = 2, fuel = 40
输出：615088286
解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。
提示：
2 <= locations.length <= 100
1 <= locations <= 10^9
所有 locations 中的整数 互不相同 。
0 <= start, finish < locations.length
1 <= fuel <= 200
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-all-possible-routes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1.自顶向下的动态规划
class Solution {
private:
int len;
int mode = 1e9+7;
public:
int dfs(vector<int>&locations, int start, int finish, int fuel, vector<vector<int> >&dp){//vector<int>&locations中加不加&会出现巨大计算时间差别！！！
if(dp != -1)return dp;
long long res = 0;
if(start == finish) res++;
for(int i = 0; i < len; i++){
if(i == start)continue;
int diff = abs(locations - locations);
if(fuel - diff >= 0){
res += dfs(locations, i, finish, fuel - diff, dp) % mode;
}
}
dp = res % mode;
return dp;
}
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
len = locations.size();
vector<vector<int> >dp(len, vector<int>(fuel + 1, -1));
return dfs(locations, start, finish, fuel, dp);
}
};
页:
[1]