单串

单串问题

确定的依赖位置

仅仅依赖之前的一个确定位置, 如i - 1,i << 1等. 因此, 在理解题意后, 可以很平滑地理清楚状态地转移.

• 338. 比特位计数
• 91. 解码方法

• 801. 使序列递增的最小交换次数

不确定的依赖位置

依赖位置有所不同.

不能直接明确地找到, 需要遍历, 或者通过之前元素的性质使用二分, 前缀和等算法优化.

• 32. 最长有效括号

• 132. 分割回文串 II

• 871. 最低加油次数

取决于两个位置

• 873. 最长的斐波那契子序列的长度
• 1027. 最长等差数列

LIS: Longest Increasing Sequence

记录最大长度

• 300. 最长递增子序列
• 354. 俄罗斯套娃信封问题($O(n^2)$可能会超时, 需要优化)
• 334. 递增的三元子序列 (特例, 可以用三指针优化时空)

记录最大长度时记录个数

• 673. 最长递增子序列的个数

记录路径

• 368. 最大整除子集

进阶: 记录所有可能路径?

多一个限制维度

单串状态机DP

• 打家劫舍
• 粉刷房子
• 买卖股票

限制子数组个数

• 813. 最大平均值和的分组
• 410. 分割数组的最大值