DP问题简介
DP问题简介
DP问题主要是解决全局最优解，与贪心不同，贪心只针对于局部最优解（后面解释dp性质时会知道原因）。
DP问题性质
- 重叠子问题(分治)：把一个大问题分成若干个处理方式相同的子问题继续解答
- 无后效性：每一个子问题对他的来源父问题没有影响(不用贪心的原因)
- 最优子结构：保证求得答案为最优解
DP问题解答步骤
在DP解答过程中，每次在求得一种状态所对应答案时，都需要调用之前已求解的状态所对应的答案
- 状态定义:状态格式及其所代表的意思
- 状态转移方程:通过一个公式来算出要求的状态(公式是自己研究出来的)
- 状态初始化:一些特殊状态的赋值(不符合状态状态转移方程)
DP题型分类
- 线性DP
- 背包DP
- 区间DP
- 树形DP
- 状态压缩DP
- 数位DP
- 计数型DP
- 递推型DP
- 概率型DP
- 博弈型DP
- 记忆化搜索
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！