C++刷LeetCode（1575. 统计所有可行路径）【动态规划】

糖逗

题目描述：

1. 给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
   
2. 
   
3. 每一步中，如果你在城市 i&#160;，你可以选择任意一个城市 j&#160;，满足 &#160;j != i&#160;且&#160;0 <= j < locations.length&#160;，并移动到城市&#160;j&#160;。从城市&#160;i&#160;移动到&#160;j&#160;消耗的汽油量为&#160;|locations[i] - locations[j]|，|x|&#160;表示&#160;x&#160;的绝对值。
   
4. 
   
5. 请注意，&#160;fuel&#160;任何时刻都&#160;不能&#160;为负，且你&#160;可以&#160;经过任意城市超过一次（包括&#160;start&#160;和&#160;finish&#160;）。
   
6. 
   
7. 请你返回从&#160;start&#160;到&#160;finish&#160;所有可能路径的数目。
   
8. 
   
9. 由于答案可能很大， 请将它对&#160;10^9 + 7&#160;取余后返回。
   
10. 
    
11. &#160;
    
12. 
    
13. 示例 1：
    
14. 
    
15. 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
    
16. 输出：4
    
17. 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
    
18. 1 -> 3
    
19. 1 -> 2 -> 3
    
20. 1 -> 4 -> 3
    
21. 1 -> 4 -> 2 -> 3
    
22. 示例 2：
    
23. 
    
24. 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
    
25. 输出：5
    
26. 解释：以下为所有可能的路径：
    
27. 1 -> 0，使用汽油量为 fuel = 1
    
28. 1 -> 2 -> 0，使用汽油量为 fuel = 5
    
29. 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
    
30. 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
    
31. 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
    
32. 示例 3：
    
33. 
    
34. 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
    
35. 输出：0
    
36. 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
    
37. 示例 4 ：
    
38. 
    
39. 输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
    
40. 输出：2
    
41. 解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。
    
42. 示例 5：
    
43. 
    
44. 输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
    
45. 输出：615088286
    
46. 解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。
    
47. &#160;
    
48. 
    
49. 提示：
    
50. 
    
51. 2 <= locations.length <= 100
    
52. 1 <= locations[i] <= 10^9
    
53. 所有&#160;locations&#160;中的整数 互不相同&#160;。
    
54. 0 <= start, finish <&#160;locations.length
    
55. 1 <= fuel <= 200
    
56. 
    
57. 来源：力扣（LeetCode）
    
58. 链接：https://leetcode-cn.com/problems/count-all-possible-routes
    
59. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1.自顶向下的动态规划

1. class Solution {
   
2. private:
   
3.     int len;
   
4.     int mode = 1e9+7;
   
5. public:
   
6.     int dfs(vector<int>&locations, int start, int finish, int fuel, vector<vector<int> >&dp){//vector<int>&locations中加不加&会出现巨大计算时间差别！！！
   
7.         if(dp[start][fuel] != -1)return dp[start][fuel];
   
8.         long long res = 0;
   
9.         if(start == finish) res++;
   
10.         for(int i = 0; i < len; i++){
    
11.             if(i == start)continue;
    
12.             int diff = abs(locations[i] - locations[start]);
    
13.             if(fuel - diff >= 0){
    
14.                 res += dfs(locations, i, finish, fuel - diff, dp) % mode;
    
15.             }
    
16.         }
    
17.         dp[start][fuel] = res % mode;
    
18.         return dp[start][fuel];
    
19.     }
    
20.     int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    
21.         len = locations.size();
    
22.         vector<vector<int> >dp(len, vector<int>(fuel + 1, -1));
    
23.         return dfs(locations, start, finish, fuel, dp);
    
24.     }
    
25. };

复制代码