1713. 得到子序列的最少操作次数

发表于 分类于 阅读次数： Waline： 本文字数： 849 阅读时长 ≈ 3 分钟

考点

  • LCS转换为LIS

思路

1. 问题概述

给定两个整数数组：

  • target：长度为 \(n\)，元素互不相同
  • arr：长度为 \(m\)，可包含重复元素

允许的操作只有一种：

在 arr 的任意位置插入任意整数

目标是：

使 target 成为 arr 的一个子序列，所需的最少插入次数。

2. 原始建模：二维 DP（插入型子序列 DP）

一种自然的建模方式是定义二维 DP： \[ f[i][j] = \text{使 } target[0..i-1] \text{ 成为 } arr[0..j-1] \text{ 的子序列所需的最少插入次数} \]

2.1 边界条件

  • \(f[0][j] = 0\)：空 target 始终是子序列
  • \(f[i][0] = i\)：arr 为空，只能插入 target 的前 \(i\) 个元素

2.2 状态转移

  • 若 \(target[i-1] = arr[j-1]\)：

\[ f[i][j] = \min\big( f[i][j-1], f[i-1][j-1] \big) \]

  • 若 \(target[i-1] \neq arr[j-1]\)：

\[ f[i][j] = \min\big( f[i][j-1], f[i-1][j] + 1 \big) \]

2.3 时间复杂度瓶颈

该 DP 的时间复杂度为： \[ O(nm) \] 在本题中 \(n, m \le 10^5\)，该方案在约束下不可行，因此需要进一步转化。

3. 从插入 DP 到 LCS 的等价变换（关键步骤）

观察 f[i][j] 的语义：

  • 若在 arr[0..j-1] 中，按顺序匹配到了 target 的 \(k\) 个元素
  • 剩余 \(i-k\) 个元素必须通过插入完成

因此必有： \[ f[i][j] = i - \text{LCS}(target[0..i-1], arr[0..j-1]) \]

3.1 定义等价变量

定义： \[ g[i][j] = i - f[i][j] \] 则有： \[ g[i][j] = \text{LCS}(target[0..i-1], arr[0..j-1]) \]

3.2 代数化推导（从 \(f\) 到标准 LCS）

  • 当 \(target[i-1] \neq arr[j-1]\)：

\[ \begin{aligned} g[i][j] &= i - f[i][j] \\ &= i - \min(f[i][j-1], f[i-1][j] + 1) \\ &= \max(g[i][j-1], g[i-1][j]) \end{aligned} \]

  • 当 \(target[i-1] = arr[j-1]\)：

\[ \begin{aligned} g[i][j] &= i - \min(f[i][j-1], f[i-1][j-1]) \\ &= \max(g[i][j-1], g[i-1][j-1] + 1) \end{aligned} \]

这正是 最长公共子序列（LCS） 的标准 DP 转移形式。

3.3 核心结论

\[ \boxed{ \text{最少插入次数} = n - \text{LCS}(target, arr) } \]

4. 为什么 LCS 可以进一步转化为 LIS

直接计算 LCS 仍需 \(O(nm)\)，但本题满足一个关键条件：

target 中所有元素互不相同

这一性质使 LCS 可降维为 LIS。

5. LCS → LIS 的构造与证明

5.1 下标映射

构造映射： \[ \text{pos}[x] = x \text{ 在 } target \text{ 中的下标} \]

5.2 序列压缩

遍历 arr：

  • 若元素不在 target 中，忽略
  • 否则用其在 target 中的下标替换

得到序列： \[ \text{seq} = [\text{pos}[arr[i_1]], \text{pos}[arr[i_2]], \dots] \]

5.3 等价性证明

  • 任意公共子序列在 target 中的下标必然 严格递增
  • 因此对应 seq 的一个严格递增子序列
  • 反之，seq 的任一严格递增子序列，对应的元素在 target 与 arr 中顺序一致

故： \[ \boxed{ \text{LCS}(target, arr) = \text{LIS}(\text{seq}) } \]

6. 最终算法

6.1 算法流程

  1. 建立 target 的值 → 下标映射
  2. 扫描 arr，生成下标序列
  3. 使用贪心 + 二分求 LIS
  4. 返回 \(n - \text{LIS}\)

6.2 时间复杂度

\[ O\big((n + m)\log n\big) \]

7. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> mp;
        for (int i = 0; i < target.size(); ++i)
            mp[target[i]] = i;
        vector<int> f;
        for (int& x : arr) {
            if (mp.find(x) == mp.end())
                continue;
            int y = mp[x];
            auto it = lower_bound(f.begin(), f.end(), y);
            if (it == f.end())
                f.push_back(y);
            else
                *it = y;
        }
        return target.size() - f.size();
    }
};