动态规划专题

1. 推导公式和结论

题目链接：一道角度推公式的dp题目,相对
题目描述：宽为2长度为m的矩阵，每一个格子有最早能够通过的时间，一个人从（0，0）出发，求每个格子经过一次且走完所有格子需要花费的最少时间。
题目思路：因为要走完所有格子且每个格子仅仅经过一次，所以只能有两种做法。对于每一条路径，发现时间恰好等于该路程上$max(a_i+后面的长度)$, 由于相对性，便可以首先记录后缀的相对最大值，再从前往后统计即可。
就是实现细节比较多。。。

2. 通过数据结构优化

题目链接：双单调队列优化和线段树记录状态
题目描述：对原序列进行划分，是每一份子序列都满足最大值再奇数位置上，最小值再偶数位置上，求所有的划分方案。
题目思路：dp的表达式很好得到，但是如果暴力的复杂度是$O(n^2)$的。对于每一个元素$a_i$考虑维护所有右端点是i的所有区间的最大值和最小值，显然，每次迭代的时候只要更新一个区间内的值，于是可以通过线段树进行维护这部分值。下面就是分类讨论了，对于1位置，对于0位置，分别维护四种状态[0|1,0|1],表示最大值和最小值是在0位置还是在1位置。通识可以使用两个单调队列分别维护需要更新的区间最大值和区间最小值。
小技巧：每个子区间奇数和偶数是相对首位置而言的，为了好维护细节，可以使用0位置表示所有偶数位置，使用1位置表示所有奇数位置。
单调队列可以维护以当前节点为右端点的所有区间的最大值和最小值，同时也可以维护部分区间的最值。

3. 令人拍手叫绝的角度和必然

题目链接：异或不为零
题目描述：给定一个$n(1\le n\le 2E5)$,求集合的个数满足：
对于该集合的所有子集合A，满足：
如果A的大小为偶数，则满足所有的A中所有数的异或值不为零。
题目思路：对于大小为i的集合而言，如何加入一个数使他仍然是满足条件的集合呢？方法是只要加入的数不等于任何一个奇数子集，又所有的奇数子集一定不相等，所有这是一个相对定值。于是通过这层转移就可以算出所有的状态个数。
设$dp[i]$表示集合大小为i的集合个数，则有公式。。。那么就可以直接使用dp进行计算即可。

4. 先贪心出一种方案，再一种方案转移出另一种方案的必然

题目链接：方案dp
题目描述：给定1000种物品，每个物品有1E18的价值和1E15的重量，且价值$c_i|c_{i+1}$, 求选出恰好k个物品且价值恰好为p的最小和最大重量。$1\le k\le 1000$
题目思路：首先贪心，不考虑物品个数，求出总价值恰好为p的最少物品个数，然后由于$c_i|c_{i+1}$，所以所有的方案都是由该方案转移而来，所以可以通过dp记录某些转移状态，实现dp。其中一个转移角度就是最后向前扔到的位置，通过这个角度就能够推导出$dp[i][j][z]$表示到达第i位，总共选了j个物品且第i个物品选了z个的最小大的重量。那么状态转移方程也可以轻易的写出。
题目经验：dp注意状态转移的时候转移全面，比如不能忘记一些边界情况

5. dp状态的设计

题目链接：dp方案的选取和设计
题目描述: 给定一个01序列，翻转相邻位置需要消耗x能量，翻转不相邻的位置需要消耗y能量，问将当前序列变成目标序列所需要消耗的最少能量。
题目思路：dp记录前面整个序列的状态为：$dp[z][i][j]$表示前i个位置有j个1且当前位置为z的需要消耗的最小能量。首先可以证明，不同位置的个数肯定为偶数，然后当不同位置个数大于4个的时候可以发现每个位置最多操作依次，于是当位置个数大于4个的时候可以枚举所有操作可能进行转移。当不同位置个数为2的时候，可以直接进行暴力。这样整个问题就能够解决了。
技巧：相对性，记录1的个数。dp是用来记录前面的状态的，不是用来记录操作的。

6. 前段状态的记录和运用

题目链接：dp状态的记录和运用
题目描述：给定一个n*n$(n\le 1500)$的矩阵，矩阵中填入了$1$到$n^2$的排列，现在要求求出所有的$2\ast 2$的子矩阵（相邻不一定连续），满足最小的连个数的连线和最大的两个数连线不相交，求这样的矩阵有多少个。
题目思路：
思路1： 考虑枚举次小值，从小往大往里面填数，对于每一个数，由于枚举的是次小值或者次大值，且有题目中要求的不相交可以知道，对于一个次大/小值，在列和行上一定分别有一个比当前数大的值和比当前数小的值，而且这个条件是充分且必要的，所以可以从小到大枚举每一个值并不断更新每行和每列的已经填充的数值的数量，这样对于当前被枚举到的值，作为次小/大值，它可以在横/纵坐标上去比它大的值，在纵/横坐标取它小的值，这样将最终的ans再/2就是最终要求的结果。
思路2：考虑在一个$2\ast 2$的矩阵中横纵从小往大连边，可以发现所有合法的方案中，度数为2的点都是1个，所有不合法的方案中，度数为2的点都是两个，所以可以统计所有矩形中度数为2的点的个数，很容易知道总矩阵个数，根据和均可以得到当前合法矩阵的个数了。

7. 用必然的结论优化dp状态转移

题目链接： 使用最后角度的必然进行dp转移优化
题目描述：给定一个序列，分别给出分成$1,2,....n$个区间所能达到的所有区间极差和的最大值。
题解：首先能够想到使用dp，对于最后一个区间，最后一个区间的左端点一定可以是一个最大值或者最小值，于是可以记录前面的这个最大值或者最小值，最终实现O（1）的转化。
通过最后的划分情况设计出状态。

8. 区间条件转化成树

题目链接：区间转换成树形dp
题目描述： 给定一个长度为n上限为m的序列$n\ast m\le 1E5$， 现在要构造出一个序列，使所有子区间的最大值最左边的位置都相同，且每一个值都是小于m的，求这样的序列有多少个。
题目思路：从最大值最左边的角度出发，发现越过这个最大值的区间不用再考虑了，只需要再单独考虑该点的左右区间，对于左右区间又可以类似的进行递归，这样就可以生成一棵树，在这棵树上就可以进行动态规划转移了。

9. 一些简单限制对dp的化简

题目链接：连续的两个数进行下取整和上取整
题目描述：给定一个树，取从根开始的k条路径，满足所有父亲节点相同的两点$u,v$经过的路径条数的差小于等于1，对于每个点都有一个价值$s_i$,每条路径的价值是所有经过的节点的价值和，求这样k条路径的最大价值和。
trick：连续的两个数除以另外一个数进行下取整和上取整最多只会产生两个值。
题解：对于每一层，都是父亲节点的类平均分配，只不过有些是上取整，可以记录他们分别的价值，然后先取下取整，再取上取整和下取整的差的前z个最大值即可求出当前子树由k条路经所能产生的最大价值，dp向上转移即可。

10. 线段树维护二维信息，使用矩阵乘法来进行懒操作

题目链接：集合多次并、与、异或，计算可能结果的大小和
题目描述：给定$1-1E6$的个区间$S_i$,求$\sum |(((S_{1}o{p}_1{S}_2)o{p}_2{S}_3)o{p}_3{S}_4)\dots o{p}_{n-1}{S}_n|$,其中op为$\cup \cap \oplus$。
题目思路：考虑每个数的所有状态，然后发现可以维护有和没有的集合个数进行状态转移，用线段树实现区间操作即可。

11. dsu on tree对树形dp进行优化

题目链接：对叶子进行染色
题目描述：每个叶子节点有一个目标颜色，每次可以选择一个节点，那么该点所有的叶子节点都会被染成该颜色，求最少的选择次数，使所有的叶子节点都达到目标颜色。
题目思路：首先必然：每个节点必然只会染色一次。对于每个子树来说，每个最优情况中，比存在情况根节点被染色，所以可以假设所有的子树根节点必然被染色。当前节点染色决定后，考虑每个子树，可以保持原来的颜色不变进行操作，也可以改变当前颜色进行操作。
关键，如果设计每个节点的集合为最优状态，那么这道题目可以使用dsu on tree进行维护。
博客：详细思路

12. 图上背包问题

题目链接：状态背包
题目描述：给定一个点1E4的图，6个需要经过的点，可以选择一些点，并只能选择一条到这一点的最短路径，使所有的路径能够覆盖京可能更多的需要经过的点，给出剩余最少的点数。
题目思路：每个可以选择的点相当于一个分组背包，用状压表示价值和重量，dp即可。

持续更新中。。。。

最后

以上就是简单路灯为你收集整理的dp好题集锦动态规划专题的全部内容，希望文章能够帮你解决dp好题集锦动态规划专题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。