文档章节

关于拆点法和DP

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

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

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

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

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

 

© 著作权归作者所有

上一篇: sgu 249
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
加载中

评论(0)

【Luogu】P2766最长不下降子序列问题(暴力网络流)

  题目链接   水题qwq,数据都那么水。   我要是出数据的人我就卡$n^3$建图。   qwq。   然而这么水的题我!居!然!没!有!1!A!!还!提!交!了!五!遍!!!   md从现在开...

osc_s6l7mhns
2018/01/11
3
0
POJ 7219 复杂的整数划分问题 【dp】【北大ACM/ICPC竞赛训练】

非常难想的题,感觉如果是第一次做的话很难做出来了。 这里问的其实有三个问题,而且相对独立,所以要分开求解。 1.整数n拆成k个正整数 dp[i][j]代表整数 i 拆成k个正整数有多少拆法,那转移...

osc_bhmyqusc
2018/07/31
2
0
【算法】leetcode算法笔记:二叉树,动态规划和回溯法

前言 写的比较匆忙,测试用例是能全部跑通的,不过考虑内存和效率的话,还有许多需要改进的地方,所以请多指教 在二叉树中增加一行 题目描述 给定一个二叉树,根节点为第1层,深度为 1。在其...

彭湖湾
2019/11/19
0
0
CCPC-Wannafly Winter Camp Day1 (Div2, onsite) A B C E F I J

A 机器人 链接:https://www.cometoj.com/contest/7/problem/A?problem_id=92 思路: 分两大类讨论: 1. B区没有点: (1)点都在起点左边 (2)点都在起点右边 (3)起点两边都有点 2.B区有...

osc_jjrjgwdy
2019/03/07
1
0
【网络流24题】最长不下降子序列(最大流,动态规划)

#【网络流24题】最长不下降子序列(最大流,动态规划) 题面 Cogs 题解 很有趣的一道题目尽管我自己还是有一些懵逼 第一问,直接大力DP一下,不解释了 第二问,考虑到一个长度为ans的子序列的...

osc_o3pzw5ip
2018/01/03
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Windows 10 中安装 Anaconda 3

首先通过下面链接地址下载 Anaconda 的个人版本。 https://www.anaconda.com/products/individual 从上面下载的地址中,选择你需要的版本,目前 Windows 应该基本上都是 64 位的了。 在你下载...

honeymoose
10分钟前
5
0
如何禁用textarea的resizable属性? - How do I disable the resizable property of a textarea?

问题: I want to disable the resizable property of a textarea . 我想禁用textarea的resizable属性。 Currently, I can resize a textarea by clicking on the bottom right corner of t......

技术盛宴
10分钟前
13
0
即时通信E聊SDK简介(1)

2.简介: E聊SDK是一套适用于PC端, 移动端的即时通讯解决方案,源代码开放。E聊整合了即时通讯的基础能力,使用E聊,您可以让您的应用快速接入即时聊天的功能。E聊现已适配PC Web, 移动Web, ...

E聊
22分钟前
9
0
多个知乎账号一起登陆,同时管理运营的神器!

随着互联网生态的优化,从2016年开始,信息内容产业相当有关注度,其和粉丝互动起来很方便、流量大到惊人、可长远发展等等优势,迅速聚集了无数企业和个人,为了有非常全面的播放数据,大家通...

易媒助手
25分钟前
22
0
403禁止vs 401未经授权的HTTP响应 - 403 Forbidden vs 401 Unauthorized HTTP responses

问题: For a web page that exists, but for which a user does not have sufficient privileges (they are not logged in or do not belong to the proper user group), what is the prope......

fyin1314
40分钟前
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部