一、最长递增子序列
这是一个非常经典的题目，该题本身比较简单，而且非常有借鉴性，可以作为模版题，很多题的解题思路可以照搬这道题。
题目解析： 作为动态规划领域的'入门标杆题'，最长递增子序列（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 {
public:
int {
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;
}
};
