文档章节

关于拆点法和DP

m2012
 m2012
发布于 2012/05/14 22:59
字数 299
阅读 89
收藏 0

拆点法和DP增加维数,动机是一样的,就是状态表示太粗糙,以至于无法转移或者求出问题的答案,所以要将一个状态拆成多个更细更具体的状态,一般的做法是,缺啥就添啥,也就是说,如果你发现:“咦,由于我不知道因素x的情况,所以我没办法转移。”ok,那你就可以尝试把因素x作为一维加到状态的表示里去。  

DP可以简单分成两种,最优化DP 和 可行性DP。有时候,如果我们没办法使用最优化DP来解决问题,那就只能通过可行性DP将可行解算出来,最后再筛选出最优解。最优化DP退化成可行性DP的时候,状态表示一般要添加新的维度。如果可以用最优化dp解决的话,尽量用最优化dp,因为最优化dp的计算过程本身就包括了可行性dp。

联想一下编译原理里面,实现一个正规表达式的状态机的时候,里面提到的概念。

 

© 著作权归作者所有

共有 人打赏支持
上一篇: sgu 249
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
求分解整数后的最大乘积 Integer Break

问题: Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. Fo......

叶枫啦啦
2017/12/26
0
0
[HDU2196]Computer(树形dp+二次扫描换根法)

版权声明:本文为博主原创文章,转载请附上原博客链接。 https://blog.csdn.net/CABI_ZGX/article/details/82989236 传送门 题意: 给出一棵树,求离每个节点最远的点的距离 一开始以为是树的...

_Mocha_
10/09
0
0
洛谷 ~ P2766 ~ 最长不下降子序列问题 (LIS + 网络流)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/82423342 第一问直接DP求解得出最长非递减子序列的长度len,f[i]表示以 i 为结尾的最...

张松超
09/05
0
0
关于积极响应中央号召坚决实行错误收集博客的通知

版权声明:myjs999原创文章 https://blog.csdn.net/myjs999/article/details/82154844   最近,中央就控制细节错误增长问题向全体员、员发出公开信,要求员带头做到一对同学只犯一个错误。...

myjs999
08/28
0
0
[LeetCode] Repeated Substring Pattern 重复子字符串模式

Output: TrueExplanation: It's the substring "ab" twice. Output: False Output: TrueExplanation: It's the substring "abc" four times. (And the substring "abcabc" twice.) public: }......

机器的心脏
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

图形用户界面和交互输入方法---图形数据的输入功能

图形数据的输入功能 输入模式 回显反馈

中国龙-扬科
29分钟前
2
0
互联网企业安全之端口监控

背景 外网端口监控系统是整个安全体系中非常重要的一环,它就像眼睛一样,时刻监控外网端口开放情况,并且在发现高危端口时能够及时提醒安全、运维人员做出相应处理。 对安全人员来说,互联网...

Skqing
31分钟前
2
0
JavaMonitor

常规监控jvm,都是比较麻烦的。但是今天在开源中国,看到了一个web版的javaMonitor。 虽然要在服务器上安装,但是这样的话,大家都能看见了。所以还是非常six的。 发现写了这个的博主也是非常...

miaojiangmin
35分钟前
4
0
Redis实践系列丨Codis数据迁移原理与优化

Codis介绍 Codis 是一种Redis集群的实现方案,与Redis社区的Redis cluster类似,基于slot的分片机制构建一个更大的Redis节点集群,对于连接到codis的Redis客户端来说, 除了部分不支持的命令外...

中间件小哥
36分钟前
4
0
HTTP常用状态码(14种)

类别 原因短语 1xx 信息型状态码 接收的请求正在处理 2xx 成功状态码 请求正常处理完毕 3xx 重定向状态码 需要进行附加操作以完成请求 4xx 客户端错误状态码 服务器无法处理请求 5xx 服务器错...

vio小黑
42分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部