很多人都不理解为什么可以用 f i 表示一个最长上升子序列大小？
那么我们可以看一下这个”上升”二字这才是这种类型问题的重点——上升要求的是什么？
不就是单调递增，即后一个比前一个大，所以只需要求这个序列的最后一个数的下标就行了。
简化题目：
在给定的序列中找不同的等差数列（可以不连续）
那么我们只需要记什么？
公差——在最长上升子序列中我们本来要求记下来最后一个数，但是我们拥有了当前下标i，所以不需要记
而这道题：
对于两个数字，他们组成的等差数列的公差一定是一样的
那么我们不必去枚举公差，直接枚举第 i 个数前面那个数，得到公差进行转移即可
用 f[i][j]表示以 i 结尾公差为 j 的等差数列个数
代码：
总结：线性DP绝大部分都是要找最优子结构的，在贪心里也是同样的，但是我们对于”模板化”的东西不能太迷恋，这也是线性dp的魅力，DP先用一个数组来描述问题答案，在去求解！
Original: https://www.cnblogs.com/qq1391197588/p/15847411.html
Author: 中指半仙
Title: 线性DP——子序列问题浅谈
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584001/
转载文章受原作者版权保护。转载请注明原作者出处！