七、其它线性 DP
七、其它线性 DP
§7.1 一维
发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i]。
2944. 购买水果需要的最少金币数 1709
2140. 解决智力问题 1709
983. 最低票价 1786
2901. 最长相邻不相等子序列 II 1899
2896. 执行操作使两个字符串相等 2172
2167. 移除所有载有违禁货物车厢所需的最少时间 2219
2188. 完成比赛的最少时间 2315
1259. 不相交的握手（会员题）
§7.2 特殊子序列
2501. 数组中最长的方波 1480
1218. 最长定差子序列 1597
1027. 最长等差数列 1759
873. 最长的斐波那契子序列的长度 1911
446. 等差数列划分 II - 子序列
1048. 最长字符串链
§7.3 矩阵快速幂优化
除了 2851 题必须用矩阵快速幂优化以外，其余题目都可以用线性 DP 做出。