2025-10-23：合并得到最小旅行时间。用go语言，给出一条总长为 l 公里、两端已标记的直路；有 n 个路标和一个整数 k

2025-10-23：合并得到最小旅行时间。用go语言，给出一条总长为 l 公里、两端已标记的直路；有 n 个路标和一个整数 k，以及两个长度为 n 的数组 position 和 time。

position 按严格递增排列，且 position[0]=0、position[n-1]=l。

对于第 i 段（即从 position[i] 到 position[i+1]），time[i] 表示每公里所需的时间（分钟/公里）。

必须恰好进行 k 次合并操作。一次合并的规则是：选取一对相邻路标（下标为 i 和 i+1，且 i>0，i+1<n），将右侧那段的单位耗时更新为 time[i]+time[i+1]，然后删除下标 i 对应的路标（即合并这两个相邻区间为一个区间，新的区间的单位耗时为两段耗时之和）。

目标是完成恰好 k 次合并后，使从 0 到 l 的总行驶时间最小化（总时间等于每个区间长度乘以该区间的单位耗时，再对所有区间求和）。

返回这个最小总时间（单位：分钟）。

1 <= l <= 100000。

2 <= n <= min(l + 1, 50)。

0 <= k <= min(n - 2, 10)。

position.length == n。

position[0] = 0 和 position[n - 1] = l。

position 是严格升序排列的。

time.length == n。

1 <= time[i] <= 100。

1 <= sum(time) <= 100。

输入: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]。

输出: 62。

解释: 合并下标为 1 和 2 的路标。删除下标为 1 的路标，并将下标为 2 的路标的时间更新为 8 + 3 = 11。

合并后：

position 数组：[0, 8, 10]

time 数组：[5, 11, 6]

总旅行时间：40 + 22 = 62 ，这是执行 1 次合并后的最小时间。

题目来自力扣3538。

动态规划解决步骤

1. 1. 预处理前缀和数组
   • • 计算一个前缀和数组 s，其长度为 n（路标数量）。
   • • s[0] = 0，对于i从0到n-2，计算s[i+1] = s[i] + time[i]。这里s[i]表示前i个路段（即从position[0]到position[i]的路段）的单位时间之和。注意time数组的第n-1个元素（最后一个元素）未被使用，因为路段数量是n-1。
   • • 前缀和的作用是快速计算任意连续路段合并后的单位时间之和。例如，合并从路标 j-sz 到路标 j 的路段时，单位时间之和 t = s[j+1] - s[j-sz]。
2. 2. 初始化三维DP数组
   • • 创建一个三维数组 f，维度为 n × (K+1) × (K+1)，其中 K 是需要进行的合并次数。
   • • f[j][sz][leftK] 表示：从路标 j 出发，当前已合并了 sz 个相邻路段（即当前区间的单位时间是这些路段单位时间之和），剩余 leftK 次合并操作时，从 j 到终点 l 的最小总旅行时间。
   • • 初始时，将所有 f[j][sz][leftK] 设置为一个极大值（表示不可行）。然后设置边界条件：当 j = n-1（即终点路标）时，对于任意 sz，如果 leftK = 0，则 f[n-1][sz][0] = 0（因为终点后无路段，时间为0）。
3. 3. 动态规划状态转移（从后往前计算）
   • • 从路标 j = n-2 开始向下遍历到 0（倒序），因为后续状态依赖于更靠后的路标。
   • • 对于每个 j，遍历当前合并大小 sz（从 0 到 min(K, j)），表示已合并的路段数（sz 不能超过 j，因为不能合并超出起点 0 的路标）。
   • • 对于每个 sz，遍历剩余合并次数 leftK（从 0 到 min(K, n-2-j)），确保剩余合并次数不超过后续可合并的路段数。
   • • 计算当前合并区间的单位时间 t：
     • • t = s[j+1] - s[j-sz]。这表示从路标 j-sz 到 j 的所有路段合并后的单位时间之和。例如，sz=0 时，t 就是 time[j]；sz=1 时，t 是 time[j-1] + time[j]。
   • • 枚举下一个子数组的起点 k（即下一个区间的开始路标），k 从 j+1 到 j+1+leftK（且 k 不超过 n-1）。对于每个 k：
     • • 计算当前区间的旅行时间：区间长度为 position[k] - position[j]，乘以单位时间 t，即 (position[k] - position[j]) * t。
     • • 子数组大小 m = k - j - 1，表示从 j+1 到 k-1 的路段数（这些路段将被合并到下一个区间）。
     • • 剩余合并次数更新为 leftK - m。
     • • 状态转移：r = f[k][m][leftK - m] + (position[k] - position[j]) * t。
   • • 取所有 k 对应的 r 的最小值，作为 f[j][sz][leftK] 的结果。
4. 4. 返回结果
   • • 最终，f[0][0][K] 即为从起点 0 到终点 l 的最小总旅行时间。其中 sz=0 表示起点未合并任何路段，leftK=K 表示恰好进行 K 次合并。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • 动态规划状态总数为 O(n × K²)（因为 j 有 n 个值，sz 和 leftK 各最多 K+1 个值）。
  • • 对于每个状态，需要枚举 k，枚举次数为 O(K)（因为 k 从 j+1 到 j+1+leftK，而 leftK ≤ K）。
  • • 因此，总时间复杂度为 O(n × K³)。由于 n ≤ 50 且 K ≤ 10，实际计算量在可接受范围内。
• • 空间复杂度：
  • • 主要开销是三维DP数组 f，大小为 n × (K+1) × (K+1)，因此空间复杂度为 O(n × K²)。
  • • 此外，前缀和数组 s 占用 O(n) 空间，可忽略不计。

该方法通过动态规划高效地枚举了所有可能的合并顺序，利用前缀和优化计算，确保了在约束下找到最优解。

Go完整代码如下：

.

package main

import (
    "fmt"
    "math"
)

func minTravelTime(_, n, K int, position, time []int)int {
    s := make([]int, n)
    for i, t := range time[:n-1] { // time[n-1] 用不到
        s[i+1] = s[i] + t // 计算 time 的前缀和
    }

    f := make([][][]int, n)
    for j := range f {
        f[j] = make([][]int, K+1)
        for sz := range f[j] {
            f[j][sz] = make([]int, K+1)
            for leftK := range f[j][sz] {
                f[j][sz][leftK] = math.MaxInt / 2
            }
        }
    }
    for sz := range K + 1 {
        f[n-1][sz][0] = 0
    }

    for j := n - 2; j >= 0; j-- { // 转移来源 k 比 j 大，所以要倒序
        for sz := range min(K, j) + 1 {
            t := s[j+1] - s[j-sz] // 合并到 time[j] 的时间
            for leftK := range min(K, n-2-j) + 1 {
                res := math.MaxInt
                // 枚举下一个子数组 [j+1, k]
                for k := j + 1; k <= j+1+leftK; k++ {
                    r := f[k][k-j-1][leftK-(k-j-1)] + (position[k]-position[j])*t
                    res = min(res, r)
                }
                f[j][sz][leftK] = res
            }
        }
    }
    return f[0][0][K] // 第一个子数组是 [0, 0]
}

func main() {
    l := 10
    n := 4
    k := 1
    position := []int{0, 3, 8, 10}
    time := []int{5, 8, 3, 6}
    result := minTravelTime(l, n, k, position, time)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

import math

def minTravelTime(_, n, K, position, time):
    # 计算前缀和
    s = [0] * n
    for i in range(n-1):  # time[n-1] 用不到
        s[i+1] = s[i] + time[i]
    
    # 初始化三维DP数组
    f = [[[math.inf] * (K+1) for _ in range(K+1)] for _ in range(n)]
    
    # 初始化边界条件
    for sz in range(K+1):
        f[n-1][sz][0] = 0
    
    # 动态规划，从后往前计算
    for j in range(n-2, -1, -1):
        for sz in range(min(K, j) + 1):
            t = s[j+1] - s[j-sz]  # 合并到 time[j] 的时间
            for leftK in range(min(K, n-2-j) + 1):
                res = math.inf
                # 枚举下一个子数组 [j+1, k]
                for k in range(j+1, j+1+leftK+1):
                    if k < n:
                        r = f[k][k-j-1][leftK-(k-j-1)] + (position[k]-position[j]) * t
                        res = min(res, r)
                f[j][sz][leftK] = res
    
    return f[0][0][K]  # 第一个子数组是 [0, 0]

def main():
    l = 10
    n = 4
    k = 1
    position = [0, 3, 8, 10]
    time = [5, 8, 3, 6]
    result = minTravelTime(l, n, k, position, time)
    print(result)

if __name__ == "__main__":
    main()

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。