第六章 - 高频考题(困难)
LCP 20. 快速公交

题目地址(LCP 20. 快速公交)

题目描述

1
小扣打算去秋日市集,由于游客较多,小扣的移动速度受到了人流影响:
2
3
小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc;
4
小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec。
5
6
现有 m 辆公交车,编号为 0 到 m-1。小扣也可以通过搭乘编号为 i 的公交车,从 x 号站点移动至 jump[i]*x 号站点,耗时仅为 cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。
7
8
假定小扣起始站点记作 0,秋日市集站点记作 target,请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大,最终答案需要对 1000000007 (1e9 + 7) 取模。
9
10
注意:小扣可在移动过程中到达编号大于 target 的站点。
11
12
示例 1:
13
14
输入:target = 31, inc = 5, dec = 3, jump = [6], cost = [10]
15
16
输出:33
17
18
解释:
19
小扣步行至 1 号站点,花费时间为 5;
20
小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台,花费时间为 10;
21
小扣从 6 号站台步行至 5 号站台,花费时间为 3;
22
小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台,花费时间为 10;
23
小扣从 30 号站台步行至 31 号站台,花费时间为 5;
24
最终小扣花费总时间为 33。
25
26
示例 2:
27
28
输入:target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]
29
30
输出:26
31
32
解释:
33
小扣步行至 1 号站点,花费时间为 4;
34
小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台,花费时间为 4;
35
小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台,花费时间为 3;
36
小扣从 33 号站台步行至 34 站台,花费时间为 4;
37
小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台,花费时间为 4;
38
小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台,花费时间为 7;
39
最终小扣花费总时间为 26。
40
41
提示:
42
43
1 <= target <= 10^9
44
1 <= jump.length, cost.length <= 10
45
2 <= jump[i] <= 10^6
46
1 <= inc, dec, cost[i] <= 10^6
Copied!

前置知识

  • 递归
  • 回溯
  • 动态规划

公司

  • 暂无

思路

这道题我们可以直接模拟所有可能性,找出最小的即可。
那么如何模拟呢?这里的模拟思路其实和回溯是一样的。我们可以使用递归控制一个变量,递归函数内部控制另外一个变量。
具体来说,我们可以用递归控制当前位置这一变量,递归函数内部循环遍历 jumps。自然语言表达就是对于每一个位置 pos,我们都可以选择我先走一步(之后怎么走不管)到终点或者先乘坐一个公交车(之后怎么走不管)到终点
核心代码:
1
def dfs(pos):
2
if pos === target: return 0
3
if pos > target: return float('inf')
4
ans = (target - pos) * inc
5
for jump in jumps:
6
ans = min(ans, 乘坐本次公交的花费)
7
return ans
8
dfs(0)
Copied!
上面代码大体思路没有问题。 只是少考虑了一个点小扣可在移动过程中到达编号大于 target 的站点。 如果加上这个条件,我们递归到 pos 大于 target 的时候并不能认为其是一个非法解。
实际上,我们也可采取逆向思维,即从 target 出发返回 0,这无疑和从 0 出发到 target 的花费是等价的, 但是这样可以简化逻辑。为什么可以简化逻辑呢?是不需要考虑大于 target 了么?当然不是,那样会错过正解。我举个例子你就懂了。 比如:
1
target = 5
2
jumps = [3]
Copied!
当前的位置 pos = 2,选择乘坐公交车会到达 2 * 3 = 6 。这样往回走一站就可以到达 target 了。如果采用逆向思维如何考虑这一点呢?
逆向思维是从 5 开始。先将 5 / 3 (整数除) 得到 1,余数是 2。 这意味着有两种到达此位置的方式:
  • 先想办法到 1,再乘坐本次公交到 3(1 * 3 = 3),然后想办法往前走 2(5 % 3 = 2).
  • 先想办法到 2,再乘坐本次公交到 6(2 * 3 = 6),然后想办法往后走 1. (3 - 5 % 3 = 1 )
这就考虑到了超过 target 的情况。
特殊地,如果可以整除,我们直接乘坐公交车就行了,无需走路 🚶。
有的同学可能有疑问,为什么不继续下去。 比如:
  • 先想办法到 3,再乘坐本次公交到 9(3 * 3 = 9),然后想办法往后走 1. (3 + 3 - 5 % 3 = 4 )
  • 。。。
这是没有必要的,因为这些情况一定都比上面两种情况花费更多。

关键点

  • 逆向思维

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def busRapidTransit(self, target: int, inc: int, dec: int, jumps: List[int], cost: List[int]) -> int:
3
@lru_cache(None)
4
def dfs(pos):
5
if pos == 0: return 0
6
if pos == 1: return inc
7
ans = pos * inc
8
for i, jump in enumerate(jumps):
9
pre_pos, left = pos // jump, pos % jump
10
if left == 0: ans = min(ans, cost[i] + dfs(pre_pos))
11
else: ans = min(ans, cost[i] + dfs(pre_pos) + inc * left, cost[i] + dfs(pre_pos + 1) + dec * (jump - left))
12
return ans
13
return dfs(target) % 1000000007
Copied!
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。