这是 LeetCode 3538. 合并得到最小旅行时间 的 TypeScript 实现。思路本题是划分型动态规划。恰好执行 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完全在时限内。---typescriptfunction minTravelTime(l: number, n: number, k: number, position: number[], time: number[]): number {// 前缀和prefix[i] time[0] ... time[i-1]const prefix: number[] new Array(n 1).fill(0);for (let i 0; i n; i) {prefix[i 1] prefix[i] time[i];}const INF: number Number.MAX_SAFE_INTEGER / 2;// dp[i][used][last]: 从 position[i] 到终点已用 used 次合并// 当前连续段的单位时间从原数组下标 last 开始累加const dp: number[][][] Array.from({ length: n }, () Array.from({ length: k 1 }, () new Array(n).fill(INF)));// 终点position[n-1]无需再行驶for (let used 0; used k; used) {for (let last 0; last n; last) {dp[n - 1][used][last] used k ? 0 : INF;}}// 从右往左填表for (let i n - 2; i 0; i--) {for (let used 0; used k; used) {for (let last 0; last i; last) {// 当前连续段的单位时间 sum(time[last..i])const rate prefix[i 1] - prefix[last];// 枚举下一个路标 j// 从 i 跳到 j 需要合并 j-i-1 次const maxJ Math.min(n - 1, i 1 (k - used));for (let j i 1; j maxJ; j) {const merges j - i - 1;if (used merges k) continue;const distance position[j] - position[i];// 下一段从 i1 开始重新累加单位时间const next dp[j][used merges][i 1];if (next INF) {dp[i][used][last] Math.min(dp[i][used][last],distance * rate next);}}}}}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 ✓
这是 LeetCode 3538. 合并得到最小旅行时间 的 TypeScript 实现。思路本题是划分型动态规划。恰好执行 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完全在时限内。---typescriptfunction minTravelTime(l: number, n: number, k: number, position: number[], time: number[]): number {// 前缀和prefix[i] time[0] ... time[i-1]const prefix: number[] new Array(n 1).fill(0);for (let i 0; i n; i) {prefix[i 1] prefix[i] time[i];}const INF: number Number.MAX_SAFE_INTEGER / 2;// dp[i][used][last]: 从 position[i] 到终点已用 used 次合并// 当前连续段的单位时间从原数组下标 last 开始累加const dp: number[][][] Array.from({ length: n }, () Array.from({ length: k 1 }, () new Array(n).fill(INF)));// 终点position[n-1]无需再行驶for (let used 0; used k; used) {for (let last 0; last n; last) {dp[n - 1][used][last] used k ? 0 : INF;}}// 从右往左填表for (let i n - 2; i 0; i--) {for (let used 0; used k; used) {for (let last 0; last i; last) {// 当前连续段的单位时间 sum(time[last..i])const rate prefix[i 1] - prefix[last];// 枚举下一个路标 j// 从 i 跳到 j 需要合并 j-i-1 次const maxJ Math.min(n - 1, i 1 (k - used));for (let j i 1; j maxJ; j) {const merges j - i - 1;if (used merges k) continue;const distance position[j] - position[i];// 下一段从 i1 开始重新累加单位时间const next dp[j][used merges][i 1];if (next INF) {dp[i][used][last] Math.min(dp[i][used][last],distance * rate next);}}}}}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 ✓
