动态规划 线性dp

为什么加了线性 dp,因为我用到的方法一部分类似最长递增子序列,就是最终答案不一定是 dp 的值,而是要在一组值里找

另外这里还有一个挺妙的点之前没遇到过,就是可以枚举公差,然后做好几遍 dp (之前的题都是一次 dp)

当公差确定了,就好做 dp 了

另外,有时候我会想要一个 hash 表来当 dp 数组,主要是为了定制化的索引,仔细想想本来 dp 数组的下标就带有含义,只是平时索引和下标意义相同

对于这道题,如果考虑到以 num 为末尾的公差为 d 的最长数量,那回头找前一个就是 num-d,很明显这里的索引应当是 num 这样的,而不是 i 这样的

然后转移也很简单,无脑+1 就好了,因为初值都是 0