动态规划解决单双序列问题
动态规划是解决复杂算法问题的利器，本文将聚焦于单序列与双序列两类经典问题，通过分析最长递增子序列、正则表达式匹配等典型案例，深入剖析动态规划的状态定义与转移方程构建思路。
一、最长递增子序列
这是一个非常经典的题目，该题本身比较简单，而且非常有借鉴性，可以作为模版题，很多题的解题思路可以照搬这道题。
题目解析： 作为动态规划领域的'入门标杆题'，最长递增子序列（LIS）不仅是面试高频考点，更是后续复杂子序列问题（如最长递增子序列的个数、二维 LIS 等）的基础模型。其核心是理解'子序列的非连续性'与'递增的严格性'，并通过动态规划将暴力枚举的高复杂度优化到可接受范围。
区分子数组（子串）与子序列：
- 子数组（子串）：在数列中的一段连续的元素组成的新数列，中间不可间断。
- 子序列：在数列中从左往右依次挑选出元素组成的新数列，或者说在数列中随意删除一些元素后，剩下的元素组成的新数列。（子序列的元素间相对位置与原数组相同）
相比之下子序列范围更大，所以也比较难。对子序列种类暴力枚举的话时间复杂度为 $O(2^n)$，对子数组种类暴力枚举时间复杂度则是 $O(n^2)$。
上题示例所示，数组 [10, 9, 2, 5, 3, 7, 101, 18]，其中单个元素就能构成一个子序列，又或者是 [2, 5]、[2, 5, 7]、[2, 5, 7, 101]、[2, 5, 7, 18]、[5, 7]、[5, 7, 101] 等等。
最长的递增子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18]，长度为 4。
算法原理 在剔除复杂度为 $O(2^n)$ 外的暴力枚举外，大家第一想到的也许是递归，每个元素都有两种选择，同样复杂度依旧为 $O(2^n)$，不过我们可以进行优化为记忆递归，时间复杂度为 $O(n^2)$，空间复杂度 $O(n^2)$，但题目并未要求得到最长的子序列的每一个元素。我们不必为此大动干戈。
要知道递归和动态规划通常可以互相转化。在讲动态规划之前需要说明一下，动态规划并不是该题的最优解，复杂度为 $O(n^2)$，而最优解是贪心算法，时间复杂度为 $O(n \log n)$，这里不做扩展。
- 确定状态表示 子数组子序列类型的动规题，我们可以尝试这里做状态表示：以某个位置为结尾的…… 所以我们做：
dp[i]表示：以i位置为结尾的所有子序列中最长的递增子序列长度。
至于该状态表示是否正确，取决于是否能推导出正确的状态转移方程。
- 状态转移方程 以如何构成这个子序列来分析问题。
dp[i] = 1，i位置的元素单独成子序列。dp[i] = 1 + max(dp[j])，其中j ∈ [0, i-1]且nums[j] < nums[i]，跟在前面的j元素为结尾的子序列后面，组成新的序列。
-
初始化 所有值初始化为最差的情况，即 1。那么
i位置的元素单独成子序列就不用再考虑。 -
填表顺序 填写
i位置时需要用到它之前的j位置，所以从前往后填表。 -
返回值 最长递增子序列可以以任意一个位置为结尾，所以最终结果是
dp表里面的最大值。
代码示例
class Solution {
:
{
n = nums.();
;
( i = ; i < n; i++) {
k = ;
( j = ; j < i; j++)
(nums[j] < nums[i]) k = (k, dp[j]);
dp[i] += k;
}
ret = ;
( val : dp) ret = (val, ret);
ret;
}
};
