文档章节

关于拆点法和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
广州
程序员
私信 提问
[HDU2196]Computer(树形dp+二次扫描换根法)

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

_Mocha_
2018/10/09
0
0
关于积极响应中央号召坚决实行错误收集博客的通知

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

myjs999
2018/08/28
0
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
洛谷 ~ P2766 ~ 最长不下降子序列问题 (LIS + 网络流)

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

张松超
2018/09/05
0
0
2018-04-04 RIA便签训练营第一次作业

作业要求:针对参加RIA便签训练营,使用 前因后果 和 适用边界 八个维度进行分析 八个维度分析(A1) 前(前车之鉴):为什么这件事对我重要? 我一直是买书如山倒,看书如抽丝的状态,买的书...

带头小哥哥
2018/04/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

嵌入式应用选择合适的微控制器

为嵌入式应用选择微控制器有几个原因,即低成本,高集成度,增加可靠性,节省空间等。 准备所需硬件接口列表使用微控制器的基本硬件框图,准备一份微控制器需要支持的所有外设接口的列表。微...

linux-tao
39分钟前
4
0

中国龙-扬科
今天
2
0
使用apicloud开发移动端APP,IOS list页面滚动卡顿解决记录

给内容容器添加样式:-webkit-overflow-scrolling:touch; -webkit-overflow-scrolling:属性控制元素在移动设备上是否使用滚动回弹效果. auto:使用普通滚动, 当手指从触摸屏上移开,滚动会立即...

万建宁
今天
1
0
Akka消息传送可靠性 23

原文:https://doc.akka.io/docs/akka/2.5/general/message-delivery-reliability.html Akka可帮助您构建可靠的应用程序,这些应用程序在一台计算机中使用多个处理器核心或分布在计算机网络中...

woshixin
今天
3
0
composer安装

前言:随着开源的东西越来越多,一些好的代码我们是可以直接拿过来用的,github更是加快了这一节奏,在github上我们可以看到一些开源的项目、代码块、函数库、类结构等,我们可以直接Fork,然...

echojson
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部