线性dp 经典线性dp 对于字符串s和t，一般定义f[i][j]表示对s[0:i]和t[0:j]的状态 最长公共子序列(LCS) 1143. 最长公共子序列 最长递增子序列(LIS) 300. 最长递增子序列 一维dp 发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i] 一维线性dp 2140. 解决智力问题(1709) 2944. 购买水果需要的最少金币数(1709) 2901. 最长相邻不相等子序列 II(1899): 还要输出具体方案 2896. 执行操作使两个字符串相等(2172): 需要先条件转换 特殊子序列dp 比较特殊的一类题型，递推比记忆化搜索好写 计算合法子序列的最长长度、个数、元素和等。 一般定义 f[x] 表示以元素(数字) x 结尾的合法子序列的 xxx 值（比如个数、元素和），从子序列的倒数第二个数转移过来。 2501. 数组中最长的方波(1480) 3202. 找出有效子序列的最大长度 II(1974) 3351. 好子序列的元素之和：一种比较不错的思路，可以通过这题理解特殊 ...