DP 总结

DP即dynamic programming一般有两种解题方式，一种是top town，另外一种是bottom up.
top down也就是常用的recursion，进一步优化可以使用memorisation，就是把其中重复计算的分支进行cache。bottom up更intuitive一些，传统bottom up时间空间复杂度是big O N, 不过也可以对bottom up算法进行优化，那就是只存相关的一个量或者两个量（n-1)或者（n-2)。空间复杂度变为big O 1.
相关题目可以刷，fibnocci number, climbing stairs and house robber。

地里揭不开锅，求大米啊！！

其实除去bottom up和top down还有另外一个（非正式）分类。
一种就是先backtrace/recursion/DFS做出来，然后加cache。这种一般比较好做出来，因为前期的部分基本等于brute force，在关键点上加上cache就可以dp优化时间复杂度。
在一种就是先判断题是否应该用dp，(指是否可以拆分成子问题，然后用子问题结果完成最终结果)。而后直接写出状态转移方程/DP公式。这种对算法要求比较高，DP公式有很多种，简单的比如Po主说出的 斐波那契，求阶乘等等。复杂的就比如race car。还有状态机dp，指每一个步骤都会有几个小状态，每个状态都由前一步的状态求得，典型例子就是股票系列。求转移方程推荐ACwing的视频，讲的比较通俗易懂。

bottom up一般比较难想一点，但通常速度会快一些

11wangyaoda 发表于 2022-11-28 21:56:50
其实除去bottom up和top down还有另外一个（非正式）分类。
一种就是先backtrace/recursion/DFS做出来，然后加cache。这种一般比较好做出来，因为前期的部分基本等于

总结的好，股票的例子很经典。再补充一点，通常DP是track一个array的状态转移，但复杂的DP会同时track多个array。多个array转移中比较简单的例子可以参考longest common subsequence

DP 相关的 labuladong 已经总结得很好了：https://labuladong.github.io/algo/3/

zichaowu 发表于 2022-11-29 05:21:06
DP 相关的 labuladong 已经总结得很好了：https://labuladong.github.io/algo/3/

这个是c++嘛 如果python 推荐看下lee215的DP总结帖

其实真的挺反感把斐波那契说成是DP的，尽管很多帖子甚至有些书都这么写。memorization只是一个优化小技巧，不能算做DP特有的。