刷lc动态规划新得总结，求加米

楼主刷了有350道题了，对于lc上的算法题有了一些了解，在此总结分享给大家(实际上想骗一波米)

DP相关经典模型:
线性dp:
数字三角形类，按照每一位置的上一步转移来划分

最长上升子序列，常规做法是枚举每个元素上一个元素是什么，可以用贪心优化到nlogn

最长公共子序列 编辑距离   此类问题关键是枚举四种情况

状态机模型: 这一步行动依赖于之前的操作序列，例题有股票4，5等

背包模型:lc上多数为01背包和完全背包，背莫版就ok

树形dp: 打家劫舍3

区间dp:lc1000，区间dp关键是先枚举区间长度，然后左右端点以及分界点

状态压缩dp:主要是二进制优化，一种是对棋盘结构进行二进制表示，还有就是对集合用二进制表示

先写这么多，希望对大家有帮助

这个link里总结的也很不错：
https://leetcode.com/discuss/gen ... rogramming-patterns
希望对大家有用。

“背包模型:lc上多数为01背包和完全背包，背莫版就ok。树形dp: 打家劫舍3”

求问莫版和打家劫舍是什么意思？
------------------------------------------------------------------
哦哦莫版应该就是模版的意思是吧，，求问有没有比较全的模版，刚开始刷题有点晕

原来不理解 学DP为啥先学背包，现在才知道 有背包的几个模板真是 太友好

区间型 应该 包含了 字符串各类前缀 后缀的模板， 还有一对 博弈论 minimax 都是 区间型

多谢总结，zszs

感谢分享

赞，感谢楼主

感谢楼主！就是想请问下，dp 其实出现的几率非常大么。。。相对于其他的内容

zzh372024750 发表于 2020/06/24 01:38:58
感谢楼主！就是想请问下，dp 其实出现的几率非常大么。。。相对于其他的内容

大厂里面比较常见，中小厂不常见

lbytenwater 发表于 2020/06/24 02:33:57
大厂里面比较常见，中小厂不常见

想拿大厂offer还是必刷的

高楼扔鸡蛋应该归为哪一类？状态机？