1575. Count All Possible Routes¶
题目信息¶
- 题号:
1575
- 难度:
Hard
- 主题:
动态规划、记忆化搜索、路径计数
- 原题:
- 重点:
城市位置互不相同,移动成本为坐标差绝对值;允许重复访问城市,并统计燃料不超限且最终停在终点的所有路线
题目重述¶
给定互不相同的位置数组 locations、起点下标 start、终点下标 finish 和燃料 fuel。从城市 i 移动到不同城市 j 会消耗 |locations[i]-locations[j]| 单位燃料。
可以访问城市任意多次,只要总消耗不超过燃料。请统计最终停在 finish 的不同路线数量;在终点继续移动后再返回也算不同路线。结果对 10^9 + 7 取模。
2 <= locations.length <= 100,0 <= fuel <= 200。
自建示例¶
燃料只够一次直接移动时只有一条路线:
输入:locations = [0,2], start = 0, finish = 1, fuel = 2
输出:1
解释:唯一可行路线是从位置 0 直接移动到位置 2。
起点就是终点且没有燃料时仍有空路线:
输入:locations = [1,5], start = 0, finish = 0, fuel = 0
输出:1
解释:不进行任何移动即可在终点结束。