适合新手入门的DP题总结【精选洛谷题集30道】

2022年01月16日 阅读数:3
这篇文章主要向大家介绍适合新手入门的DP题总结【精选洛谷题集30道】,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。


0.总结


  • 文章来源:CSDN@LawsonAbs
  • 简述解答dp问题时常有的思想
  • 列举笔者刷题时遇到的较为简单的DP练习,已经对这些题目的思考【题目来自洛谷】


1.主要思想

动态规划(dp)问题是编程从入门到进阶的一个分水岭,能够这么说:几乎任何一份有质量的题中都有dp的影子。【固然,我这里的dp指的是广义上的递推】这也就是数学中的逻辑思惟的体现,将获得的代码手动敲出代码实现,就是物理中的实证思惟的体现。因此说编程可以体现一个IT人员的基本素养,而dp问题则是能力的主要试金石。算法

这里笔者总结了常见的dp入门题,但愿可以帮助到相关人员。以下是我总结出处理dp问题时,总结到的一些经验。编程


  • 抽象看问题!从一个问题中,肯定出哪些因素是关键因素?是什么致使问题的变化?是什么致使状态的变化?
  • 转换问题。解题时,尽可能把题目转化为已学的模型,好比背包;​​LCS​​;​​LCIS​​等等
  • ​dp​​中,不一样的操做体如今对维度的操做上。对各个维度取不一样值时选择其最优解。​​dp​​问题无非就是找出相应的维度。
  • 如何肯定问题的状态?如何肯定状态的转移方程?
    问题一般由哪些要素决定?若是由哪些要素决定,一般就是有几种维度。

2.案例分析

2.1.1 P1439【模板】最长公共子序列


  • step1.离散化处理第一个序列
  • step2.根据第一个序列离散化的结果求出第二个序列最长不降低子序列的长度便可。

2.1.2 P1103书本整理


  • step1.肯定问题是什么,再想可否转化问题。
    就这题来讲,能够知道,其实题目就是要求出,在去掉k本书以后,获得剩余序列相邻元素间差的绝对值的和的最小值。
  • step2.转换问题以后,其实去掉k本书,就至关于选n-k本书。
  • step3.选哪本书是一个操做,操做用于决定维度。这时就能够猜想书的序号是不是一个维度。【好比选第i本应该就是f[i]】
  • step4.上一步骤中选出的书处于什么位置也应是一个维度【本身动手模拟时,就会发现,选不选都会改变书的最终位置】。好比选出的第i本书,处于从左至右的第j本,不一样的j取值也不相同。这时就获得了一个二维状态数组f[i][j]。

2.1.3 P1140 类似基因

这道题讲的是如何求出两个序列的最大类似值。数组

针对两个序列能够增添一个‘-’字符用于匹配。本题的难点也就是在于这个‘-’字符的处理。可是若是定义好了维度就会发现很简单。ide

有两个序列,(求最大类似值),是否是让咱们想到了LCS,相似的定义,就有f[i][j]表示A1-Ai 与序列B1-Bj 所能达到的最大类似值。因而。测试


  • step1. 定义f[i][j]表示A1-Ai 与序列B1-Bj 所能达到的最大类似值。
  • step2.对于每一个f[i][j]都可由f[i-1][j]【Ai匹配-】,f[i][j-1]【-匹配Bj】,f[i-1][j-1] 【Ai匹配Bj】推导而来

2.1.4 P1020导弹拦截

问题转化,问须要几枚导弹才能把全部的目标都拦截?优化

其实就是给定一个序列,让你求出最长上升子序列的长度。编码

有几个问题须要注意一下:spa


  • 导弹能够不连续拦截
    3 6 2 4(3,2),(6,4)分两波拦截,只须要两个导弹。而不是须要(3)(6,2),(4)三个导弹。
    3 6 2 3 4
    能够这么理解,第二问能够用“最长上升子序列”来求是由于:
  • 01.对于最长上升子序列中的元素,知足若i<j,有Ai < Aj。当Ai被以前的导弹击中时,Aj必须被另一个新的导弹击中,若是是同一个导弹击中,是不符合题意的。(导弹不可能先去击中Aj,再去击中Ai,由于是先出现Ai,再有Aj)。同理,对于任何一个最长上升子序列相邻的元素都是这么分析,设其长度为len,则需导弹len个。
  • 02.最长上升子序列的一些性质也是颇有意思的
    【递增状况:(3 4 5)】假设有序列:(3 4 5 1 2 3),其LIS为(1 2 3)或(1 2 3)。能够看到在1位置以前的元素是没有比1更小的了,不然1不会是LIS的第一个元素,(由于咱们求的是LIS,如有更小的,确定会把它算成LIS的一部分)。
    因此能够前面的任何一个炮弹打完以后均可以把1顺带消灭;同理分析LIS中的2,3都是如此。

【递减状况:(5 4 3)】假设有序列:(5 4 3 1 2 3),其LIS为(1 2 3)。很显然,再也不分析。翻译

【有增有减(5 3 4)】假设序列(5 3 4 1 2 3),其LIS为(1 2 3)。由于(3 4)并非LIS,因此必定能够在消灭LIS以前把(3 4)消掉。其他同理分析。code

其实

2.1.5 P1435回文字串

这题有两种解决方法,分别是LCS和 区间DP。这里采用LCS来作。

方法1:LCS

主要是问题的转换。原文题等价于求出LCS。至于为何这么作,我尝试将个人思路说给你们听听。


  • step1.有原串s1 = abdca
  • step2.取其倒序串s2= acdba。【为何取倒序串?由于要使字符串回文,因此就须要倒着念。】
  • step3.找出s1与s2的LCS。针对上面的字符串,能够发现(aba),(ada),(aca)均可以是LCS。【这个LCS是回文的,由于它们正着读和反着读的结果是同样的】
  • step4.也就是说字符串s1在变成回文串以前已经有LCS是回文的了,令LCS的长度为len,因此相应的只须要针对剩下的n-len个字符便可。

2.1.6 P1470 [USACO2.3]最长前缀 Longest Prefix

这题其实就是一个彻底背包的变题。主要思路以下:

给出一个集合,集合中是若干个字符串,再给出一个字符串s。判断由集合中的元素组成的字符串s的前缀最大长度是多少?

若是将集合中的每一个字符串当作是物品,每一个字符串能够放无限次。其长度就是该字符串的价值。可是不一样于朴素的彻底背包,放下物品(字符串)的时候,不只须要判断以前的前缀是否可达,还要判断接下来若干长度的字符串长度是否匹配。好比测试用例

A AB BA
.
AABAA

在放集合中的第一个元素的时候,最大前缀可达2,在匹配第三个的时候由于A!=B 失败了。

本题须要注意的点是:循环的层次。我曾像彻底背包那样使用双层for循环【第一层遍历物品(即这里的集合),第二层遍历价值(即这里的前缀)】,结果倒是错误的。正确的是,第一层先遍历价值,第二层再遍历集合。

2.1.7 P1474 [USACO2.3]Money System / [USACO07OCT]Cow Cash G

类彻底背包。

主要思路,依次放入前i个物品,而后判断到达价值j时的方案数,依次累加便可。

2.1.8 P1481 魔族密码

相似LIS 问题

只不过这里的“上升子序列”的定义方式是:若一个字符串s1的前缀是另一个字符串s2,则由s2,s1构成的序列则是上升的。

实现的时候须要注意:应该初始化f[]为0,而后在输出的时候输出max(f[i])+1,由于题目要求输出最长单词链中单词的个数。

2.1.9 P1504 积木城堡

相似0/1背包问题

有n个问题,每一个问题都是0/1背包问题。让求出这n个问题中共同的最大的价值(即本题的高度)。

2.1.10 P1566 加等式

简单的0/1背包问题

只须要判断集合中每一个元素可到达的方式种类,最后再减去集合中元素的个数便可。

2.1.11 P1586 四方定理

本题的问题主要有:


  • 1.如何确保只有4个数之内的平方和到n?
  • 2.如何避免重复?好比25 = 3^2 + 4^2 = 4^2 +3^2 ,但实际上,这两种状况只看作一次。
  • 3.dp题难道只能用dp的算法作吗?
    固然不是,对于本题,咱们甚至能够用4重for循环来暴力枚举。

主要方法

方法1:dp

其实本题是一个类彻底背包的问题。

设f[i][j]表示 数i可由j个数的平方和表示的个数,其中j取值范围为1-4;转移的方程为:若是f[j-squ[i]][0-3]>0,则 f[j][(0-3)+1] += f[j-squ[i]][0-3]; 这么作是不会形成 25 = 3^2 + 4^2 = 4^2 +3^2 这样的重复解。由于放数字的是有顺序的,【在本题中,也就是按照先放3,再放4的顺序来的】

可是有以下几个技巧:


  • 咱们不用对于每一个n都去计算其解的个数,这样会致使重复解。相反正确的作法是求出输入数据范围以内的最大值maxT,而后计算maxT内全部整数的解,而后针对输入数据,直接输出结果,不然复杂度会很大。我由于“相信本身思想没错”致使交了数次的TLE代码。就是由于重复解了不少次致使超时。
    这题侧面也说明了要多动脑,少改代码!
  • 在四重for循环中,须要注意剪枝和避免重复解。咱们能够按照i<=j<=k<=l 这样的大小关系,枚举四个循环。

bfs可用于求朴素版的最短路。之因此说是朴素版,就是由于其搜索的图中的顶点间的边没有边权(或者说权重值都是相同的);或者是单纯的搜索次数就是“优越性”的比较。但若是在一个不是以走的路径次数为优先的题目中,就很难肯定最优解。例如络谷的P1649题。

2.1.12 P1649 [USACO07OCT]Obstacle Course S

这题打上dp的标签是想说明dp的过程就是不断更新迭代的过程吗?

主要思想


  • 使用bfs不断更新到达坐标(cx,cy)须要转弯的次数。
  • 队列中的数据类型是Node,其包含的元素是坐标(x,y),转弯次数tN,到达该点时的方向dir。
  • 不断的进出队,找到最优解便可。

本题坑点:

  • 不要仅仅觉得只有当转弯的次数更低时,才可入队。由于每次入队都是有方向的,不一样方向的入队但转弯次数相同时,会对后续的序列形成影响。【这种问题的缘由归根结底是:判断一个元素是否更优的条件取决于多个因素(本题不只取决于转弯次数,还和转弯的方向有关),当你只判断了其中部分因素(我只选择步长更短的入队,而无论其方向),就致使得不到最优解,从而WA! 】

2.1.13 P1681 最大正方形II

很简单的dp算法

主要思想:

  • f[i][j]指的是坐标点(i,j) 取到的最大值。
    考虑坐标得到在左上方向的最大正方形的边长。【可能有人会问,那么不用考虑右上方向的最大正方形了吗?是的,不用了,由于这两个方向是等价的】转移方程以下:
if(arr[i][j]!=arr[i-1][j] && arr[i][j]!= arr[i][j-1] 
&& arr[i][j] == arr[i-1][j-1]){
f[i][j] = min( min(f[i-1][j],f[i][j-1]),
f[i-1][j-1])
+1;
}

2.1.14 P2004领地选择

主要思路

有两种方法解决这道题目。

方法一:

使用row[i][j]记录 第i行前j列数的和; col[i][j]记录第i列前j行的和。在遍历二维坐标点的时候,找出以该坐标点为方形左上角元素时,获得的最大和。获得方形元素的最大和的方法是:


  • 判断第j列时,将第j-1列所在正方形中的和从cur中去掉,同时加上第j+c-1列的和
  • 判断第i行时,将cur置零。从新获取以坐标(i,1)开始的正方形的和。

方法二

使用二维数组的前缀和。这个很好写,建议使用这种方式。

2.1.15 P2904 [USACO08MAR]River Crossing S

主要思路:

方法1:

我刚开始拿到这道题,没有想太多。直接写成了贪心。40分!!!由于局部最优得不到全局最优。而后明白应该用以前的每头牛去更新当前的牛所须要的最小价值。

rec[i]表示第i头牛是船中的第几头牛; dp[i]表示第i头牛过河须要的最短期

方法2:

仔细思考这题,就会发现这题实际上是一道简单的背包问题(我更倾向于认为这是个0/1背包)。将一次运送1,2,……i头牛的代价分别记为d[i],则须要找出一个运送方案(其实就是加数集合)使得d[n]最小便可。

转移方程就是: ​​d[i] = min(d[i],d[j+]d[i-j]+d[0]);​

2.1.16 P1754 球迷购票问题

问题转换!!

本题和P1044 栈很像!【将售票员拿到50元当作是入栈操做,售票员找零50元当作是出栈操做,因而问题就转换成n个50元有多少个出入栈的次数问题,也就是1-n这n个数,在出入栈以后,有多少个不一样的排列次序问题。】

将实际的问题抽象成二维坐标点,而后根据状态的转移,获得递推方程,从而获得解。下面分别分析。

问题1:

  • dp[i][j]表明已经来了i个50的人和j个100的人时的方案数;【问题就在于如何想到是这么定义得?】
    那么分两种状况
if(i>j)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];//若是来的50的多于100的,那么此次来50和100的均可以
}
else if(i==j)
{
dp[i][j]=dp[i][j-1];//若是100和50的同样多,那么此次只能来50的
}

实现的时候,只须要让i>=j恒成当即可。

  • 我本身定义状态时,还出现了相对 手拿50元的球迷在队中的数目的判断。若是到n了,则中止入队,这是递归的思想,但不是递推。

2.1.17 P1233 木棍加工

疑问是:

01.为什么在将长度排完序以后,从宽度就能够获得最优解了?为什么是最优解?

2.1.18 P2690[USACO04NOV]Apple Catching G

主要思想

  • 令dp[i][j][k] 表示 第i分钟,用j次移动,在树k下 获取的最大值 。知道状态以后,就好搞转移方程了。【必定要先在纸上写下来,再写代码!!!!很是重要】。

坑点:


  • 01.移动的奇偶次数关系很重要!不然结果会多算摘到的苹果。其根本缘由是,不是全部状况下的 k与arr[i]相等时,就能够摘到,而要符号条件的移动次数。
  • 02.移动次数要从0开始枚举到w
  • 03.题面说:奶牛不肯意不停地往返于两棵树之间。 不知道是翻译的问题,仍是题面的问题,这个要求是没有体如今代码中的。

2.1.19 P3252 [JLOI2012]树

主要思路

dfs+剪枝

搜索每一个节点,若是和到s,则返回,不然继续深搜,直到和超过s,或者到达边界。

剪枝操做是:若是该点的子孙节点的全部和都不能到达s,那么就不用再遍历其子孙节点。

2.1.20 P2196 挖地雷

主要思路:

深搜便可

给出地窖中的地雷信息,每一个地窖的链接信息,求出能够从任一个地窖出发能够排查出的最大地雷数。

2.1.21 P5146 最大差值

水题一道。

边记录,边找出最小的值,而后用当前的值减去已经找到的最小值。用res记录差值的最大,最后输出res便可。

2.1.22 P2725 [USACO3.1]邮票 Stamps

这题要变换思路。

将其转换成背包来作。须要注意的问题就是,令dp[i]为到达价值i所需的最小邮票数,而不是dp[i]=1表示价值i可达。【这种令法在dp题中很常见!!】 若是是像后者那么假设,则会获得一个错误的3重for循环。

for(int i = 1;i<=k;i++){//放第i张    
for(int j = maxV;j>=0;j--){//价值j
for(int l = 1;l<n;l++){
...
}
}
}

作dp题不能死板,要根据题意灵活使用模板。

2.1.23 P6208 [USACO06OCT]Cow Pie Treasures G

简单的dp题。

直接给出了显性的坐标了,就等于说明这是一道水题了。

主要思路


  • 令dp[i][j]表示坐标(i,j)可达的最大值。
  • 按照先列后行的顺序遍历便可,在遍历过程当中,不断的将dp[i][j]得成最大值。

坑点:

并非全部的点均可以进行移动的,好比说,最开始只有坐标(1,1)能够往右移动,可是(2,1),(3,1)就没有资格往右移动。【因此说即便由(2,1)出发构成最大值也是不能要的。因此用个标记数组标记,只能从已经访问过的坐标开始往右遍历。】

2.1.24 P3133 [USACO16JAN]Radio Contact G

简单的递推。

须要注意的点有:


  • 1.问题的转换
    根据每一个人每次走的方向,获得一个二维坐标的序列。题目的含义就至关于要求每两个坐标点(分别是A,与B)对应上取得的最小值。
  • 2.dp数组初值的设置
    令dp[i][j]表示在A在序列i,B在序列j时,可以达到的最大值。

学会从题目中获得解题信息。好比:

  • 当看到n的值较小时,只有百级别,那么就能够考虑O(n^3)的算法,开数组时,也能够开出多维数组。

2.1.25 P1103 书本整理

dp题的关键是如何设置状态转移方程。

本题,不少人都能令 dp[i][j]是从前i本书中选出j本书所可以达到的最小不整齐度。可是还有一个关键点是:dp[i][j]表示的是第i本书要被放到这j本书中【也就是做为这j本书的最后一本】。 可能会有人问为何?可是我想说,为何要问为何?

若是dp[i][j] 就是从前i本书中选出j本书。那么当咱们更新从前i本书中取出j本书时获得的最小不整齐度时,咱们的更新值是须要用当前加入的这本书同上一次放(j-1本)书的宽度值做为新的损耗值加进来,可是这时问题就来了,咱们怎么知道上一次放(j-1)本书结尾的那个宽度值?

即便你用数组rec[i][j]表示从前i本书中选出j本书时,第j本书的编号。你只是用这个数组来存储,可是你没有定义它是怎么放的,因此仍然没法肯定这个rec[i][j]值该取什么。就拿一个特殊的例子,

rec[1][1] = 1? 
rec[2][1] = 1? 2?
rec[3][1] = 1? 2? 3?
……

因此,必须定义清楚,由于这涉及到dp更新的问题,是个关键问题,在编码以前就必须考虑清楚。

题目中有什么重要元素,就应该考虑将这个重要元素做为一个维度存储起来。

2.1.26 P2782 友好城市

水题一道。【可供dp新手练习时间复杂度为O(NlogN)的最长不降低子序列长度】

主要思路

仍是问题的转换。

  • 要不相交的通航道。从x坐标来看,从小到大的建航道,若是不相交,就等价于南部城市Xi建好以后,其友好城市为Ai;接着建下一个城市Xj,新建的航道城市必须是在城市Ai更靠右的【更靠右的特征就是一个不降低的特征】。从而能够发现其实本题就是让咱们在以南端城市顺序从小到大排序以后,求北端城市的一个最长不降低子序列。

2.1.26 P2049 魔术棋子

不是全部的DP标签题都要用dp解。例如本题。

主要思路

方法一:

用bfs遍历每一个点,用set集合存储每一个点所能到达的值的集合。【确定是须要保存的,用于提供给后续的点】


  • 对输入数据预处理,arr[i] %= k;
  • 从初始点开始bfs,每次bfs的时候,对当前点的值集合进行遍历,乘上即将要走到的点B的值,而后放到B的值的集合中。
  • 队列遍历结束时,整个任务就完成了。输出最后一个点的集合便可。

优化的方法:

直接用一个三维数组arr[x][y][z]存储点(x,y)可否到达值z。数组大小也就1e3。因此比用set更好。

bfs能够解决dfs深搜带来的重复问题。【不少题dfs解都会十分复杂,可是bfs则是较优的方案】

方法二:使用dp

dp[x][y][z] 表示在位置(x,y)是否能够获得值z。而后一个简单的三重for循环便可。

for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int l=0;l<k;l++) //由于mod k 后获得的数必定小于k,因此从0到k枚举
if(!dp[i][j][l*num[i][j]%k]) //没有计算过
dp[i][j][l*num[i][j]%k]=dp[i-1][j][l]||dp[i][j-1][l]; //l*num[i][j]%k表示当前格子数乘从左边或上边传下来的数l再mod k,dp[i-1][j][l]和dp[i][j-1][l]表示在上方或左方能不能获得l

方法三:深搜

若是想用深搜,恐怕朴素的深搜不大好使【很差剪枝(我太菜),只有20分】。分太少,主要是由于打开深搜的方式不对。

同上面的定义,判断点(x,y)在取值z时是否访问过,若是访问过,则再也不深搜,不然深搜,这样就能够避免重复的搜索了。这要求咱们和dp解题同样,定义一个数组为:vis[x][y][z],深搜时注意重复便可。

能够看到不管是深搜,仍是广搜,仍是dp,其实质上的数组维度都是同样的,都是三维【在set版本的bfs中,其set至关于第三维】。这些是巧合吗?

2.1.27 P3399 丝绸之路

简单的dp题,仔细分析一下,有点儿像背包,但实质上不是背包。

能够发现,问题就是在M天内到达城市N,求最小的疲劳度。根据求什么设什么的原则,咱们能够令dp[i][j] 为前i天到达城市j,花费的最小疲劳度 。【求什么设什么是一个高度总结,新手可能会问为何,可是仔细想一想,就应该是这样。】

主要思路


  • dp[i][j] 为前i天到达城市j,花费的最小疲劳度
  • 用前一天的值与当前的值作比较,并始终取最小值便可。循环中的主要语句以下:

dp[i][j] = dp[i-1][j];
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+ d[j]*c[i] );

2.1.28 P2426 删数

本题要转化问题。感受洛谷的题都是这个样子,

2.1.29 P1833 樱花

背包问题的组合题。【多重背包】该物体有使用次数限制,【彻底背包】该物品能够无限次使用。

针对题意能够有以下朴素思路:


  • 1.若是物品是无数个数目,则用彻底背包实现
  • 2.若是物品是有限个数目,则用多重背包实现
    可是这样的实现复杂度很高,能够考虑采用 二进制拆分,将一个物品拆成若干个相似物品,最后再用0/1背包解决问题。

2.1.30 ​​P1004 方格取数​

看到数N的取值范围是<=9。那么就能够想到是否能够有不少重循环来解决这个问题。几乎都是这样的,事实证实这题的朴素作法就是要用一个四维数组来搞。

主要思路:

方法1

f[i][j][k][l] 表示两我的到坐标(i,j),(k,l)所能达到的最大值。而后不停的进行更新便可。须要注意的是,若是(i,j) = (k,l),那么就不能加两倍的数。

方法2:


  • 找阶段
    能够发现两种行走路径所到达的终点坐标(x1,y1),(x2,y2) 存在以下关系:
    x1+y1 = x2 + y2。同时,令i为行走的步数【步数是依次增长的,能够将其看作是DP中的阶段】,那么同时也有:x1+y1 = x2 + y2 = i+2。
  • 找状态
    因而咱们能够用 (i,x1,x2) 来惟一表达出一个“状态”。这个状态的含义就是“在行走了i步以后,分别到达(x1,y1),(x2,y2)所能达到的最大值”
  • 找决策
    这题中的决策很容易就能发现,分别是走法。两个路径分别有两种走法,合计就是4种走法。对于这个决策咱们不须要使用for循环来表示,相反直接使用几个if循环判断就能够了。