对DP的一点感想

时间:2022-08-24 23:53:11

复习DP的过程中还是略有收获。

首先是改掉了原来的一个愚蠢错误:区间DP要注意以长度为阶段进行转移,不要傻乎乎地枚举左右端点就了事了,怎么WA的都不知道。

有一个新发现: ”所有数字互不相同的“ LCS可以转化为LIS。《算法竞赛入门经典》有这样的一道题。不过NOIP很少考这种模板题吧。

然后写了各种类型的:LIS,LCS,LCIS,地图上,区间上,树形DP……还是积累了一点经验。

因为严格的“DP”(不是递推)解决的是最优方案问题,所以它跟搜索也有一定的相似之处。如果搜索树中的节点计算需要大量祖先节点的信息,那大概就只有搜索了。但在一些情况下,节点信息只需要父亲结点或者部分祖先节点推出,就可以用DP解决。

不过DP的实质是隐式DAG上的遍历,跟搜索还是有一定区别。但和搜索还是有千丝万缕的联系。

所以我爱上了记忆化搜索:使用递归,简单易写,不用考虑DAG拓扑序,有些情况下甚至优于一般的递推。

缺点也很明显:常数大易爆栈。我写的某道状压记忆化还不如直接DFS+剪枝。自己还是太天真。

明天挂一个总结。