文档章节

关于拆点法和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。

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

 

© 著作权归作者所有

共有 人打赏支持
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
关于积极响应中央号召坚决实行错误收集博客的通知

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

myjs999
08/28
0
0
洛谷 ~ P2766 ~ 最长不下降子序列问题 (LIS + 网络流)

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

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

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

带头小哥哥
04/04
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

没有更多内容

加载失败,请刷新页面

加载更多

中秋快乐!!!

HiBlock
55分钟前
1
0
Node安装教程

1、安装最新版的node 2、设置相关目录(以D盘为例) 分别建立目录:D:\node,D:\node\node-globa,D:\node\node-cache 命令行输入: // 设置npm国内镜像 npm config set registry https://re...

Mohan710
今天
3
0
中国发布域名系统基础软件 “红枫”

9月12日消息,域名工程中心(英文缩写 ZDNS)发布了宣称自主开发的域名系统基础软件 “红枫(Maple DNS)”。 9月12日消息,域名工程中心(英文缩写 ZDNS)发布了宣称自主开发的域名系统基础软...

问题终结者
今天
3
0
Shell编程(分发系统介绍、expect远程登录、expect远程执行命令、expect传递参数)

分发系统介绍expect 分发系统expect即分发脚本,是一种脚本语言;通过他可以实现传输,输入命令(上线代码) 应用场景:业务越来越大,网站app,后端,编程语言是php,所以就需要配置lamp或者...

蛋黄_Yolks
今天
4
0
Java Http请求工具类

public static String httpPost(String source, String params) {URL url = null;HttpURLConnection conn = null;OutputStream os = null;String ret = null;try {......

yuewawa
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部