atc 经典dp 26题 题型总结

题目链接
稍微记录下吧。主要想发现他 这个题单主人 是怎么去分类dp的类型的。借鉴
题目不一定要多难。但是题型的分类总结 感觉很重要。
某种dp的处理方式。。他是相似的。。
A B 数组 前面往i+1 ，i+2.。。这样的推 。
C 限制只能 交叉继承。。不能继承pre一样位置的 。他每层有三个位置。
D 01 背包
E 也是01背包 但是这里容器W 1e9.巨大…但是开销很小。。
反过来吧开销当做容器。。然后反向计算当前开销所需要容器的最小可能🔥
统计答案的时候反向枚举 开销 第一个需要的容器<=W的时候就是答案。

F 找两个string的公共最长 子序列。不连续的那种。主要恢复手法 i-- j-- 。
LCS 的本质就是一个填表的过程 dp的填表视角就是基于这种题型吧。

G Longest Path. DAG 求最长路。。就是一个top模版。。也可以记忆化dfs🔥
也不用强行写dp 写的非常麻烦。还过不去。费力不讨好。。这东西top很好写。。
H - Grid 1. 矩阵的[1,1]->[n,m]的路径数统计 就是f[i-1][j].f[i]j[j-1]来。