ToB企服应用市场:ToB评测及商务社交产业平台

标题: DP条记 [打印本页]

作者: 冬雨财经 时间: 2024-6-1 00:16
标题: DP条记
DP条记

目次

DP条记

一、动态规划总结

要使用动态规划须要哪些条件？

最优子结构
子问题重叠
无后效性

1 和 2 中只须要满足一个，再加上 3，接下来就可以愉快地使用动态规划了。
动态规划把原问题分别为若干子问题，每个子问题的求解过程构成一个阶段，求解完前一个阶段再求解后一个阶段。根据无后效性，动态规划的求解过程构成一个有向无环图，求解的顺序就是该有向无环图的一个拓扑排序。
以下是处理动态规划问题的 基本要素：

确定状态、保存状态变量
即计划dp数组，保存当前状态。这个状态就是每个子问题的决策。常常：问什么就设什么。
分别阶段、计划决策方法
即计划状态转移方程。常常：根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
处理界限
即计划一个终止条件或界限条件。

以下是处理动态规划问题的 基本步调：

状态定义： 每个状态的决策，存放每个状态的变量。
状态转移方程： 当前状态与上一个状态之间的关系。
初始状态： 初始的状态或者界限条件。

二、线性DP

使用场景相对暗昧：通常是有显着的子问题重叠。
状态有多个维度，每个维度都是线性分别的阶段，团体呈现递推的形式。
**状态定义： ** 基本上是问什么设什么。答案即是dp数组的值。
**状态转移方程： ** 分清楚阶段，找到子问题。通过子问题推出当前的状态。
界限条件： 一般比较清楚。(数据的界限)
重点： 先要分维度，再找到可以用于递推的子问题。这两个步调要一起举行，数据范围可能会提示维度怎样分，在此基础上计划出一种可以递推出答案的方法。最后按照维度循环得到答案。
例题：走楼梯，最长上升子序列，最长公共子序列。
三、背包问题

详见背包九讲。
四、区间DP

使用场景很显着：处理区间问题，得到某种最优答案。
区间dp的秘籍就是： i 到 j 的这个区间的所期望求的值可能是 i 到 k 的值和 k+1 到 j 的值通过某种方式合并得到。
很显着越大的区间要覆盖更小的区间所得到的值。
状态定义： dp[j] 表现：i 到 j 这个区间的答案。有的时候会在加上一维 k (0/1)，表现某一段选或者不选。
状态转移方程： dp[j] = combine(dp[k], dp[k][j]); //k: i ~ j combine () 是一种合并的方式，有的时候是取最大最小，偶然是相加，还有可能是其他。
重点： 区间dp的第一层循环大多是遍历区间长度，接着循环起点（留意起点要合理，加上长度后不超过终点的范围），由循环得到的起点可以推出终点。最后再举行状态的转移。核心是找到合并两个区间的答案的方法。
例题：[P1880 [NOI1995] 石子合并]
dp[j] 表现：取 i ~ j 的最大得分
在 [i, j] 这一区间内，枚举下标k举行拆分。
合并 [i, k] 与 [k+1, j] 的区间，会加上 [i, j] 之间所有石子个数之和。
得到状态转移方程为 f[j]=max(f[j], f[k]+f[k+1][j]+sum[j]-sum[i-1]);
其中sum为前缀和
[code]for (int len = 2; len

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4