algorithm-dp-linear

线性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. 好子序列的元素之和：一种比较不错的思路，可以通过这题理解特殊子序列dp

矩阵快速幂优化dp

请看快速幂

子矩阵dp

• 3148. 矩阵中的最大得分(1820)

多维dp

• 3336. 最大公约数相等的子序列数量