这是 LeetCode 3538. 合并得到最小旅行时间 的 Python3 实现。思路本题是划分型动态规划。恰好执行 k 次合并等价于将原路标序列切分为 n-k 个连续段每段的单位时间为该段内所有 time 之和。状态定义 dp[i][used][last] 表示- 当前位于第 i 个路标- 已经用了 used 次合并- 当前连续段的单位时间从原数组下标 last 开始累加转移 从 i 跳到 jj i消耗 j-i-1 次合并当前段距离为 position[j]-position[i]单位时间为 sum(time[last..i])。复杂度 O(n² × k²)由于 n ≤ 50, k ≤ 10完全在时限内。---pythonclass Solution:def minTravelTime(self, l: int, n: int, k: int, position: list[int], time: list[int]) - int:# 前缀和prefix[i] time[0] ... time[i-1]prefix [0] * (n 1)for i in range(n):prefix[i 1] prefix[i] time[i]INF float(inf)# dp[i][used][last]: 从 position[i] 到终点已用 used 次合并# 当前连续段的单位时间从原数组下标 last 开始累加dp [[[INF] * n for _ in range(k 1)] for _ in range(n)]# 终点position[n-1]无需再行驶for used in range(k 1):for last in range(n):dp[n - 1][used][last] 0 if used k else INF# 从右往左填表for i in range(n - 2, -1, -1):for used in range(k 1):for last in range(i 1):# 当前连续段的单位时间 sum(time[last..i])rate prefix[i 1] - prefix[last]# 枚举下一个路标 j# 从 i 跳到 j 需要合并 j-i-1 次max_j min(n - 1, i 1 (k - used))for j in range(i 1, max_j 1):merges j - i - 1if used merges k:continuedistance position[j] - position[i]# 下一段从 i1 开始重新累加单位时间nxt dp[j][used merges][i 1]if nxt INF:dp[i][used][last] min(dp[i][used][last], distance * rate nxt)return dp[0][0][0]---验证- 示例 1l10, n4, k1, position[0,3,8,10], time[5,8,3,6] → 62 ✓- 示例 2l5, n5, k1, position[0,1,2,3,5], time[8,3,9,3,3] → 34 ✓