单双序列问题——动态规划
单序列问题往往具备两个关键特征，使其特别适合用动态规划求解。
- 问题解决路径需拆解为多个步骤，每个步骤都存在多种选择，最终目标是计算可行解的总数，或是找到满足条件的最优解。
- 问题的输入数据通常呈现为序列形态，比如一维数组、字符串等典型的线性数据结构。
根据题目的特点找出该元素对应的最优解（或解的数目）和前面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程。一旦找出了状态转移方程，只要注意避免不必要的重复计算，问题就能迎刃而解。
接下来看几个适合运用动态规划的单序列问题。
一、最长递增子序列
这是一个非常经典的题目，本身比较简单，而且非常有借鉴性，可以作为模版题，很多题的解题思路可以照搬这道题。
题目解析： 作为动态规划领域的'入门标杆题'，最长递增子序列（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 位置，所以从前往后填表。
