这是 LeetCode 3538. 合并得到最小旅行时间 的 Java 实现。思路本题本质是划分型动态规划。恰好执行 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完全可行。---javaimport java.util.Arrays;class Solution {public int minTravelTime(int l, int n, int k, int[] position, int[] time) {// prefix[i] time[0] time[1] ... time[i-1], prefix[0] 0int[] prefix new int[n 1];for (int i 0; i n; i) {prefix[i 1] prefix[i] time[i];}final int INF Integer.MAX_VALUE / 2;// dp[i][used][last]: 从 position[i] 到终点已用 used 次合并// 当前连续段的单位时间从原数组下标 last 开始累加int[][][] dp new int[n][k 1][n];for (int i 0; i n; i) {for (int j 0; j k; j) {Arrays.fill(dp[i][j], INF);}}// 终点position[n-1]无需再行驶for (int used 0; used k; used) {for (int last 0; last n; last) {dp[n - 1][used][last] (used k) ? 0 : INF;}}// 从右往左填表for (int i n - 2; i 0; i--) {for (int used 0; used k; used) {for (int last 0; last i; last) {// 当前连续段的单位时间 sum(time[last..i])int rate prefix[i 1] - prefix[last];// 枚举下一个路标 j// 从 i 跳到 j 需要合并 j-i-1 次int maxJ Math.min(n - 1, i 1 (k - used));for (int j i 1; j maxJ; j) {int merges j - i - 1;if (used merges k) continue;int distance position[j] - position[i];// 下一段从 i1 开始重新累加单位时间int 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 ✓