线性图中选K条无重叠顶点的最小权边：优化O(NK)解法

问题背景 #

给定N个顶点的路径图，需选出K条顶点不重叠的边，使总权值最小。现有动态规划解法时间复杂度为O(NK)，以下是优化时间复杂度的核心思路：

1. 二进制提升（Binary Lifting） #

针对K较大的场景，可将K分解为二进制形式，通过预计算快速组合出最优解：

• 预构建两个二维数组：
  • cost[i][m]：表示从第i条边开始选2^m条不重叠边的最小权值；
  • end[i][m]：表示选完2^m条边后最后用到的顶点位置（下一条需从end[i][m]+2开始）；
• 递推关系：cost[i][m] = cost[i][m-1] + cost[end[i][m-1]+2][m-1]，end[i][m] = end[end[i][m-1]+2][m-1]；
• 最终遍历K的二进制位，累加对应2^m的最小权值即可得到结果；
• 时间复杂度：O(N log K)，空间复杂度：O(N log K)。

2. 分治优化（Divide and Conquer Optimization） #

利用动态规划状态转移的四边形不等式性质，将每层k的计算时间从O(N)降至O(N log N)：

• 原DP状态dp[k][i] = min(dp[k][i-1], dp[k-1][i-2] + w[i])满足分治优化的适用条件；
• 对每个k，通过分治递归处理区间，记录每个位置的最优决策点，避免重复计算；
• 总时间复杂度：O(NK log N)，虽未摆脱K的线性依赖，但常数大幅降低，适合K中等大小的场景。

3. 线段树辅助动态规划 #

通过线段树维护前序DP状态的最小值，加速当前层的计算：

• 计算dp[k][i]时，选择第i条边的代价为dp[k-1][i-2] + w[i]，线段树可快速查询前序状态的最小值（适配更通用的区间查询场景）；
• 时间复杂度：O(NK log N)，实现更灵活，适合需要扩展的问题场景。

4. 最小费用流建模 #

将问题转化为最小费用最大流问题，求解K单位流的最小成本：

• 拆分每个顶点为入点和出点，入点到出点连容量1、费用0的边（避免顶点重叠）；
• 每条原边对应一条从u出点到v入点的容量1、费用为边权的边；
• 源点连到起点出点，终点入点连到汇点，容量均为K、费用0；
• 求解最小费用流得到K条边的最小权值总和，适合K较小的场景，时间复杂度：O(K(N + N log N))。

内容的提问来源于stack exchange，提问作者fmatt