960. 删列造序 III

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

考点

  • LIS
  • 状态设计

思路

一、问题重述（Problem Restatement）

给定一个字符串数组 \[ \text{strs} = [s_0, s_1, \dots, s_{n-1}] \] 其中每个字符串长度相同，记为 \(m\)。

允许删除若干列（对所有字符串同时删除相同的列），目标是使得：

对于任意一个字符串 \(s_k\)，删除后的字符序列是非递减的。

要求删除的列数最少。

二、建模视角的关键转化

1. 从「行」视角转为「列」视角

该问题的关键并不在于单个字符串，而在于列与列之间的相对关系。

将第 \(j\) 列视为一个整体： \[ C_j = (s_0[j], s_1[j], \dots, s_{n-1}[j]) \] 每一列是一个长度为 \(n\) 的字符向量。

2. 列之间的“可连接”关系

若在最终保留的列序列中，列 \(j\) 位于列 \(i\) 之前（\(j < i\)），则必须满足： \[ \forall k \in [0, n-1],\quad s_k[j] \le s_k[i] \] 即： \[ C_j \preceq C_i \quad \text{（逐维不大于）} \] 这是一个偏序关系（partial order），而非全序。

3. 问题的等价表述

在原列顺序不变的前提下，寻找一个最长的列子序列 \[ j_1 < j_2 < \dots < j_t \] 使得 \[ C_{j_1} \preceq C_{j_2} \preceq \dots \preceq C_{j_t} \]

若该最长长度为 \(L\)，则最少删除的列数为： \[ m - L \]

三、动态规划建模（LIS-like DP）

1. 状态定义

令： \[ f[i] = \text{以第 } i \text{ 列结尾的最长合法列子序列长度} \] （这里的下标 \(i\) 表示列索引）

2. 状态转移

对于每个 \(i\)，枚举所有 \(j < i\)： \[ f[i] = \max\Bigl( 1,\; \max_{\substack{j<i \\ C_j \preceq C_i}} (f[j] + 1) \Bigr) \] 其中判定条件为： \[ C_j \preceq C_i \iff \forall k,\; s_k[j] \le s_k[i] \]

3. 初始化与答案

  • 初始： \[ f[i] = 1 \quad (\text{至少保留自己这一列}) \]

  • 最终保留的最多列数： \[ L = \max_i f[i] \]

  • 最小删除列数： \[ m - L \]

4. 时间复杂度

  • 枚举列对：\(O(m^2)\)
  • 每次比较两列需检查所有字符串：\(O(n)\)

总复杂度： \[ O(m^2 \cdot n) \] 在题目给定约束下是可接受的。

四、为什么不能使用 \(O(n\log n)\) 的 LIS 模板

1. LIS 的 \(O(n\log n)\) 本质依赖什么？

经典 LIS（patience sorting + 二分）依赖以下关键前提：

  1. 元素之间存在全序关系 任意两个元素都可比较大小；
  2. 存在“尾部最优”的贪心替换原则： 用更小的尾值替换，不会影响未来扩展。

2. 本题中的列比较是「偏序」

列之间的关系是： \[ C_a \preceq C_b \iff \forall k,\; s_k[a] \le s_k[b] \] 这是一种逐维支配关系（dominance order），常见特点是：

  • 可能存在 \(C_a\) 与 \(C_b\) 互不可比
  • 无法定义一个一维的“大小”来排序所有列

例如（两行示意）： \[ C_1 = (1,3), \quad C_2 = (2,2) \]

  • \(1 \le 2\) 但 \(3 \nleq 2\)
  • \(2 \nleq 1\)

两列不可比较。

3. 贪心失效的根本原因

  • 无法维护单调的 tails[]
  • 无法用二分定位替换位置
  • 不存在“更小尾部一定更优”的交换论证

因此：

本题是 偏序集上的最长链问题（Longest Chain in Poset）， 而 \(O(n\log n)\) 的 LIS 只是一维全序上的特殊情况。

结论是： 只能使用 \(O(m^2)\) 级别的 DP，而不能套用 LIS 的 log n 模板。

五、编程实现要点总结

  1. 列索引作为 DP 的“时间维”
  2. f[i] 表示以第 \(i\) 列结尾的最长合法子序列
  3. 判定条件是「所有字符串逐行不下降」
  4. 结果是 m - max(f[i])

六、AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 1e2 + 5;
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size(), m = strs[0].size(), res = 0, f[maxn];
        for (int i = 1; i <= m; ++i) {
            f[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                bool flag = 1;
                for (int k = 0; k < n; ++k) {
                    if (strs[k][i - 1] < strs[k][j - 1]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                    f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        return m - res;
    }
};