Hard

题目描述

给你一条长度为 l 公里的直线道路，一个整数 n，一个整数 k，以及两个长度均为 n 的整数数组 position 和 time。

数组 position 按严格递增顺序列出了标志的位置（以公里为单位）（其中 position[0] = 0 且 position[n - 1] = l）。

每个 time[i] 表示在 position[i] 和 position[i + 1] 之间行驶 1 公里所需的时间（以分钟为单位）。

你必须执行恰好 k 次合并操作。在一次合并中，你可以选择任意两个相邻的标志，索引为 i 和 i + 1（其中 i > 0 且 i + 1 < n），并：

  • 更新索引 i + 1 处的标志，使其时间变为 time[i] + time[i + 1]
  • 移除索引 i 处的标志

返回在恰好 k 次合并后，从 0 到 l 的最小总旅行时间（以分钟为单位）。

示例 1：

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

输出：62

示例 2：

输入：l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]

输出：34

约束条件：

  • 1 <= l <= 10^5
  • 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

解题思路

这是一个复杂的动态规划问题。我们需要理解合并操作的本质：合并两个相邻标志会移除中间的标志，使得新的段的时间成本变为两个原段时间的和。

核心思路：

  1. 状态定义：使用三维DP，dp[i][j][s] 表示考虑前 i 个位置，已经进行了 j 次删除操作，在位置 i 之前连续删除了 s 个标志时的最小旅行时间。

  2. 状态转移：对于每个位置 i，我们有两种选择：

    • 保留当前标志：重置连续删除计数，添加当前段的旅行时间
    • 删除当前标志：增加连续删除计数和总删除计数

  3. 旅行时间计算：当我们保留位置 i 时，需要计算从上一个保留位置到当前位置的旅行时间。如果中间删除了 s 个连续标志，那么这段的时间成本就是所有被合并段的时间之和。

  4. 边界条件：第一个和最后一个位置必须保留（起点和终点）。

算法步骤：

  1. 初始化DP数组，第一个位置的状态
  2. 对每个位置进行状态转移
  3. 在最后一个位置中选择恰好进行了k次删除的最小值

这个解法的时间复杂度为O(n³k)，空间复杂度为O(n²k)，在给定的约束条件下是可行的。

代码实现

class Solution {
public:
    int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {
        const int INF = 1e9;
        // dp[i][j][s] = min time for positions 0..i, j deletions total, s consecutive deletions before i
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(n, INF)));
        
        // Base case: position 0 is always kept
        dp[0][0][0] = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int s = 0; s < i && s <= j; s++) {
                    if (i == n - 1 && j != k) continue; // Must use exactly k deletions
                    
                    // Keep position i (reset consecutive deletions)
                    if (s < i && dp[i - s - 1][j - s][0] != INF) {
                        int timeSum = 0;
                        for (int t = i - s - 1; t < i; t++) {
                            timeSum += time[t];
                        }
                        int travelTime = (position[i] - position[i - s - 1]) * timeSum;
                        dp[i][j][0] = min(dp[i][j][0], dp[i - s - 1][j - s][0] + travelTime);
                    }
                    
                    // Delete position i (if not the last position)
                    if (i < n - 1 && j < k) {
                        dp[i][j + 1][s + 1] = min(dp[i][j + 1][s + 1], dp[i][j][s]);
                    }
                }
            }
        }
        
        return dp[n - 1][k][0];
    }
};

class Solution:
    def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:
        INF = float('inf')
        # dp[i][j][s] = min time for positions 0..i, j deletions total, s consecutive deletions before i
        dp = [[[INF] * n for _ in range(k + 1)] for _ in range(n)]
        
        # Base case: position 0 is always kept
        dp[0][0][0] = 0
        
        for i in range(1, n):
            for j in range(k + 1):
                for s in range(min(i, j + 1)):
                    if i == n - 1 and j != k:
                        continue  # Must use exactly k deletions
                    
                    # Keep position i (reset consecutive deletions)
                    if s < i and dp[i - s - 1][j - s][0] != INF:
                        time_sum = sum(time[i - s - 1:i])
                        travel_time = (position[i] - position[i - s - 1]) * time_sum
                        dp[i][j][0] = min(dp[i][j][0], dp[i - s - 1][j - s][0] + travel_time)
                    
                    # Delete position i (if not the last position)
                    if i < n - 1 and j < k:
                        dp[i][j + 1][s + 1] = min(dp[i][j + 1][s + 1], dp[i][j][s])
        
        return dp[n - 1][k][0]

public class Solution {
    public int MinTravelTime(int l, int n, int k, int[] position, int[] time) {
        const int INF = 1000000000;
        // dp[i][j][s] = min time for positions 0..i, j deletions total, s consecutive deletions before i
        int[,,] dp = new int[n, k + 1, n];
        
        // Initialize with INF
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int s = 0; s < n; s++) {
                    dp[i, j, s] = INF;
                }
            }
        }
        
        // Base case: position 0 is always kept
        dp[0, 0, 0] = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int s = 0; s < i && s <= j; s++) {
                    if (i == n - 1 && j != k) continue; // Must use exactly k deletions
                    
                    // Keep position i (reset consecutive deletions)
                    if (s < i && dp[i - s - 1, j - s, 0] != INF) {
                        int timeSum = 0;
                        for (int t = i - s - 1; t < i; t++) {
                            timeSum += time[t];
                        }
                        int travelTime = (position[i] - position[i - s - 1]) * timeSum;
                        dp[i, j, 0] = Math.Min(dp[i, j, 0], dp[i - s - 1, j - s, 0] + travelTime);
                    }
                    
                    // Delete position i (if not the last position)
                    if (i < n - 1 && j < k) {
                        dp[i, j + 1, s + 1] = Math.Min(dp[i, j + 1, s + 1], dp[i, j, s]);
                    }
                }
            }
        }
        
        return dp[n - 1, k, 0];
    }
}

var minTravelTime = function(l, n, k, position, time) {
    const memo = new Map();
    
    function dp(pos, t, merges) {
        if (merges < 0) return Infinity;
        if (pos.length === 2) {
            if (merges === 0) {
                return (pos[1] - pos[0]) * t[0];
            }
            return Infinity;
        }
        
        const key = `${pos.join(',')}|${t.join(',')}|${merges}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = Infinity;
        
        // Try merging each valid pair
        for (let i = 1; i < pos.length - 1; i++) {
            const newPos = [...pos];
            const newT = [...t];
            
            newT[i] = t[i-1] + t[i];
            newPos.splice(i-1, 1);
            newT.splice(i-1, 1);
            
            result = Math.min(result, dp(newPos, newT, merges - 1));
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp([...position], [...time], k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n³k)
空间复杂度O(n²k)

其中 n 是标志数量，k 是合并操作次数。由于约束条件限制了 n ≤ 50，k ≤ 10，所以这个复杂度在实际应用中是可接受的。