概述
依据：1.不重 2.不漏
不过并不是这两个条件每一次都需要满足
在求数量的时候1一定要满足，再求min和max的时候1可以不满足
但是不漏一定要遵守
一般的dp划分依据：
1.按照最后一步来划分
dp的计算顺序问题：
（按照拓扑序）
dp状态一般怎么表示：
如果是网格图就是f[i,j]
线性图就是f[i]
如果是背包问题的话，就是第一维是物品，第二维是体积
背包问题的循环顺序不能随便变，但是一般的只要符合拓扑序就行
本质上来说dp是图论的一小部分
百分之九十的dp都能转化成最短路
当我们的图，是拓扑图的时候，可以把最短路问题转化成dp问题
当我们的dp设置完之后，发现它的状态不是拓扑图了，我们可以用最短路解决
状态表示：每一个都代表一个集合，它必须是有意义的，而且每一个都能推出来我们的答案
状态计算：找到一种方式能够算出来每个集合的值
对于lis，除了贪心之外，还有一些数据结构可以优化成nlogn，比如（离散化）线段树，平衡树，
最后
以上就是老实老鼠为你收集整理的dp的划分的全部内容，希望文章能够帮你解决dp的划分所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复