dp 总结 1
dp 总结 1闲来无事, 把刚学明白的 dp 笔记整理一下.
shout out to professor Adzlpxsn.
基本的, 状态, 转移, 方程
状态
一句话概况即为当前的属性.
比如说, 贝贝现在是 \(30\) 岁, 发了 \(0\) 张专辑, 我们就可以说 \(f_{30}=0\).
这里我们说 \(30\) 和 \(0\) 是不同的信息, 所以一个状态 \(f_{x}=y\) 里包含的信息其实有 \(x\) 和 \(y\).
同样的, \(f_{x,y}=z\) 里包含的信息有 \(3\) 个, 即 \(x\) \(y\) \(z\).
转移
转移, 就是说用 \(f_{x}\) 推算 \(f_{y}\), 或者用 \(f_{x}\) 和 \(f_{y}\) 推算 \(f_{z}\).
举个例子.
贝贝的新专辑 "金手指", 第 \(x\) 首歌是 boombap 还是 trap 取决于第 \(x-1\) 首和第 \(x-2\) 首, 即 \(f_{x}=(f_{x-1}+f_{x-2}) \bmod 2\). 那么我们就说 \(f_{x}\) 由 \(f_{x-1}\) 和 \(f_{x-2}\) 转移而来.
方程
方程就是把转移的过程写成人类能看懂的东西, 比如 "数学语言" "自然语言" "编程语言".
线性 dp
最简单的线性 dp, 就是跳跃问题.
problem:AtCoder-dp_a
考虑状态, 我们让 \(f_{x}\) 表示现在位于 \(stone_{x}\) 时最少跳了多少.
转移就比较容易了, \(f_{x}=\operatorname{std::min}(f_{x-2}+|h_{x-2}-h_{x}|,f_{x-1}+|h_{x-1}-h_{x}|)\).
没什么好讲的, 注意边界条件初始化就好了, 难的题就很难.
背包 dp
这个就好玩了.
01 背包
我个人觉得背包 dp 和线性 dp 大抵是有血缘关系的罢.
problem:AtCoder-dp_d
可以想到, 我们让 \(f_{c}\) 表示在背包容量为 \(c\) 时的最大价值.
于是有转移方程 \(f_{c}=\operatorname{std::max}(f_{c},f_{c-w_{x}}+v_{x})\).
那么这时候我们有一个问题.
如果内层循环从 \(w_{x}\) 枚举到 \(W\), 那么有可能会造成重复选择, 但题意说每个物品只有 \(1\) 个.
于是我们可以调转内层循环的方向, 从 \(W\) 枚举到 \(w_{x}\), 此时每个物品就只会被选一次了.
代码
for(ll x=1;x 热心回复！ 鼓励转贴优秀软件安全工具和文档！ yyds。多谢分享 分享、互助 让互联网精神温暖你我 谢谢楼主提供！ 谢谢分享，辛苦了 用心讨论，共获提升！ 分享、互助 让互联网精神温暖你我 懂技术并乐意极积无私分享的人越来越少。珍惜 分享、互助 让互联网精神温暖你我 这个有用。 谢谢分享，辛苦了 东西不错很实用谢谢分享 收藏一下 不知道什么时候能用到 这个有用。 不错，里面软件多更新就更好了 鼓励转贴优秀软件安全工具和文档！ 东西不错很实用谢谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！
页:
[1]
2