最长上升子序列(LIS)

1. \mathcal{O}(n^2) 做法

dp_{i} 表示以i 结尾的答案。所以先枚举一个 i ,再从1 开始枚举 j ,每次看到小于 a_{j} 的数,取一个最大的更新 dp_{i}

2. \mathcal{O}(nlog_n) 做法

状态设计: dp_i 表示长度为 i 的最长上升子序列的最小末尾值。
思想解读:一条上升子序列长度确定,末尾越小越容易使一个元素在后面加入。

两个序列中的最长公共子序列(LCS)

1. \mathcal{O}(n^2) 做法

dp_{i,j} 表示第一个序列前 i 位,第二个序列前 j 位的解的长度。
如果当前的 A_i = B_idp_{i,j} = max(dp_{i – 1, j – 1}+1, dp_{i, j})
如果当前的 A_i \neq B_idp_{i,j} = max(dp_{i-1,j}, dp_{i,j-1})

2. \mathcal{O}(nlog_n) 做法

考虑一个 map ,表示 A_iB 中的位置。
如果 A_iB 中递增,则考虑它。

第二个序列为第一个序列的最小子串的子序列问题

1. \mathcal{O}(n^2) 做法

直接暴力枚举 l 向右匹配。

2. \mathcal{O}(n) 做法

考虑到每种字符在 t 中至多出现一次,所以每个字符往后想要跳到什么字符是固定的,因此并不用对每个位置维护一个长度为 mm 的数组。

不难发现 s 出现次数最少的 t_i 是不会超过 \frac{n}{m} 次的。因此我们令 c 表示在 t 中出现且在 s 中出现次数最少的字符,然后把选择每个等于 t_1 的位置开始做改成每个等于 c 的位置,然后同时向前向后跳。

时间复杂度 \mathcal{O}(\frac{n}{m} \cdot m) = \mathcal{O}(n)

3. \mathcal{O}(n) 做法

考虑使用 m-pointers。从后往前枚举 l,然后同时维护一个长度为 m 的数组 p,表示当前 l 开始,往后 t 中的所有字符,会在 s 中的哪里匹配。不难发现 p_i 会更新当且仅当 p_{i−1} 有更新。因此每次我们直接暴力更新一个前缀即可。

不难发现 s 中每个字符至多被匹配一次,因此时间复杂度 O(n)

4. \mathcal{O}(n) dp

例题 – 七里香