Leetcode 3538. Merge Operations for Minimum Travel Time

• Leetcode 3538. Merge Operations for Minimum Travel Time
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3538. Merge Operations for Minimum Travel Time

1. 解题思路

这一题思路上就是一个动态规划的思路，我们只需要考察每一个位置如果不进行merge的情况与进行merge的情况，然后取其中的较小值即可。

其中，如果不进行merge，那么当前段路程的速度就是当前节点下的速度，其下一段的速度就是time序列当中下一段节点的速度。

反之，如果当前结果要进行merge，那么当前节点的速度依然保持为之前记录的当前节点的速度，而其下一段的速度就是在之前记录的下一段速度的基础上加上time序列中下一个节点的时间。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:
        
        @lru_cache(None)
        def dp(idx, k, present, nxt):
            if idx + k == n-2:
                return present * (l - position[idx])
            if k == 0:
                return present * (position[idx+1] - position[idx]) + dp(idx+1, k, nxt, time[idx+2])
            return min(
                present * (position[idx+1] - position[idx]) + dp(idx+1, k-1, present, nxt + time[idx+2]),
                present * (position[idx+1] - position[idx]) + dp(idx+1, k, nxt, time[idx+2]),
            )
        
        return dp(0, k, time[0], time[1])

提交代码评测得到：耗时253ms，占用内存47.4MB。