单串问题是什么

单串问题是线性动态规划中最简单的一类题，通过输入一串数，即数组，考虑 [0..i] 上原问题的解。而原问题的最优解，最常见的就是取 i 位置上的解，当然也有不在 i 上的情况，我们先只讨论取 i 位置的解的情况。

  1. 最优解依赖比 i 小的 O(1) 个子问题：
    i 只与前面固定个数的子问题有关，如斐波那契数列 斐波那契数列 只考虑 i - 1 和 i - 2 的解。
    练习题：跳台阶
  2. 最优解依赖比 i 小的 O(n) 个子问题：
    i 与 [0..i-1] 的子问题都有关，比如之前《Prologue - 简述动态规划》 举过的例子（最长递增子序列）他的转移方程为
     dp[n] = max(dp[n-1]..dp[0]) + 1
    练习题：单词拆分

练习：单串LIS系列

1 最长上升子序列

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
题解：https://blog.nowcoder.net/n/afb199c4bf0b4eda86c0588d1eff9177
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2

输入：nums = [0,1,0,3,2,3]
输出：4

示例3

输入：nums = [7,7,7,7,7,7,7]
输出：1

2 最长递增子序列的个数

链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
给定一个未排序的整数数组，找到最长递增子序列的个数。

示例1

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例2

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

3 俄罗斯套娃信封问题

链接：力扣 或牛客
题解：https://blog.nowcoder.net/n/3328691dd49f4dc88f028c068feb24ba
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例1

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例2

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1