线性动态规划
|
老官童鞋gogo
|
121
|
0
|
数据结构,程序设计
|

4519 字
|
27 分钟

线性动态规划规划简介

在所有动态规划中，线性动态规划的难度最低，同时线性动态规划也是所有动态规划的基础。

顾名思义，线性动态规划就是说动态规划的过程在“一条线”上进行，状态转移只有一个方向。最常见的线性$\rm{DP}$有子集和问题，$\rm{LIS}$问题，$\rm{LCS}$问题，字段和问题等。其实，线性$\rm{DP}$的用处不只如此，很大一部分的的杂类问题都可以转化为线性$\rm{DP}$。

线性动态规划的基础应用

求解$\rm{LIS}$问题

$\rm{LIS}$指的是最长上升子序列问题，即给定一个序列，在这个序列中找出一个子序列，满足元素严格单调递增，求满足条件的最长的子序列的长度。解决这个问题，我们可以类比解决最长下降子序列问题、最长不上升子序列问题、最长不下降子序列问题。解决$\rm{LIS}$问题存在$O(n^2)$和$O(n \log n)$两种解法。

$O(n^2)$做法

首先研究其解决问题的过程。我们需要把一个大的问题变成一个小问题，在这个问题中，我们每一步需要考虑的是判断我们当前选的这个数是否能和前面的数接上，如果当前的数大于前面的数，就能接上去，这个序列的长度会变长一位。但是，前面可能会有很多种组成不同序列的方法，我们应该接在哪个序列之后呢？原题目问的是最长的上升子序列，我们就直接接在前面我们已经决定了的最长的序列后就可以了，因为无论我们后面怎么接，前面的序列都已经被确定，不会改变，现在接了最长的，以后也一定是最长的，这满足了动态规划的无后效性。

根据这个方法，我们设计状态。因为我们要研究的是当前数字接上上一个数字所构成的$\rm{LCA}$的长度，所以我们可以设$dp[i]$，表示以第$i$位数字结尾的最长上升子序列的长度。然后根据状态设计转移方程，首先我们要找到前面所有求出来的最长的上升子序列的长度，所以我们需要枚举前面所有$DP[j]$的值，选出符合条件的最大的值（第$i$数大于第$j$个数即为符合条件），然后将最大的值加一，最终转移方程即为：$dp[i]=\max\{dp[j]\}+1(j\in[1,i-1],a[j] \lt a[i])$。

考虑边界条件与初始化，边界即为$n$，初始化为全部为$1$，因为一个数字自己构成一个子序列。最终答案即为$\max\{dp[i]\}(i\in[1,n])$。

for(int i=1;i<=n;i++){
    dp[i]=1;
	for(int j=1;j<i;j++){
		if(a[i]>a[j])
			dp[i]=max(dp[i],dp[j]+1);
	}
}

$O(n \log n)$做法

$n^2$做法并不够快，考虑有没有一种更快的做法。

在$O(n^2)$的做法中，有一步过程很费时间，就是枚举之前所有求出的答案并找出最大值。我们修改状态，设置$dp[i]$表示以这个最长上升子序列。但是我们只记录一个最长的序列，设置$len$记录下从一开始到当前数字的最长上升子序列长度，如果当前数字$a[i] \gt dp[len]$时，说明我们可以直接将这个数接到这个最长子序列后。如果$a[i] \lt dp[len]$，那么我们要找到$dp[]$这组数字中大于这个数的最小的数，并将其替换掉，因为$dp[]$这个数组时有序的，所以可以使用二分查找，将时间缩到$\log n$。

但是为什么要替换掉呢，现在假如说我们替换掉了那个数，并且不看序列中后面的数，可以发现，前一部分的数仍然是$\rm{LCA}$，如果我们不换，最后那个数会比交换后最后那个数大，很显然，两个相同长度的上升子序列中，最后一个数越小，它后面接数的可能性越大，所以我们直接替换掉。

现在我们考虑后面的数字，这就出现了两个问题：

  • 为什么要替换掉，而不在前面插入，这样上升序列的长度不会更长吗？

    然而事实是，你现在替换的这个数不能直接插入到前面已经排好的序列中，因为插入操作会改变原有序列的相对位置，这样构成的就不是序列了，而是排列。

  • 为什么替换后不会影响到后面的结果？

    假设你替换的那个数不是已经排好的序列的最后一个数，那么你替换掉它，不会影响到序列中最后一个数与原序列后面的数的比较，反而更新了一种更优的答案。假设你替换的数正是已经排好的序列中的最后一个数，那么你替换掉它，就说明这一整个序列被你更新了，换成了一个更优的$\rm{LIS}$序列，为什么更优，看第一个问题的解释。总而达到无后效性。

转移方程变成$dp[++len]=a[i](a[i]\gt dp[len]),dp[p]=a[i](a[i]\lt dp[len],p为dp数组中大于a[i]的最小的数的位置)$，边界条件不变，初始化为$dp[1]=a[1],len=1$，最终的答案就是$len$的值。

dp[1]=a[1],len=1;
for(int i=2;i<=n;i++){
	if(dp[len]<a[i])
		dp[++len]=a[i];
	else{
		int p=upper_bound(dp+1,dp+1+len,a[i],greater<int>())-dp;
		dp[p]=a[i];
	}
}

求解$\rm{LCS}$问题

$\rm{LCS}$指最长公共子序列，即给定两个序列，在两个序列中分别找出一个子序列，使得找出的这两个子序列完全相同，求满足条件最长的两个子序列的长度。

我们要求最长的公共子序列，首先要保证它是公共的，即要保证选出的两条子序列的长度是相同的，也要保证其中每一位上的元素也是相同的，现在，假设我们已经求出了第一条子序列中第$x$个位置前的与第二条子序列中第$y$个位置前的最长公共子序列，现在要处理的就是第$x$位和第$y$位，如果这两个元素相同，就直接把最长长度加$1$，如果不相同，就去掉第$x$位或者是第$y$位，比较每一段序列的前一位，二者取最大值。因为这里我们匹配不上了。

由此，我们设状态$dp[i][j]$表示第一个序列$x[1\sim i]$与第二个序列$y[1\sim j]$的最长公共子序列的长度，转移方程分出三种情况：

$$dp[i]=\begin{cases}\max\{dp[i-1][j],dp[i][j-1]\},&x[i]\neq y[i]\\dp[i-1]j-1]+1,&x[i]=y[i]\end{cases}$$

初始化即为$dp[i][0]=0,dp[0][j]=0$，边界即为$n,m$，$n,m$分别表示两个字符串的长度最终答案即为$dp[n][m]$。

for(int i=1;i<=n;i++)
    dp[i][0]=0;
for(int j=1;j<=n;j++)
    dp[0][j]=0;
for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		if(a[i]!=b[j])
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		else
			dp[i][j]=dp[i-1][j-1]+1;
	}

最大连续字段和

这里给出一个序列，我们要求出这个序列中最大的连续字段和，注意，这个序列中是存在负数的！

首先寻求解决问题的方法。因为字段是连续的，所以无论哪一个字段，都会以一个数开始，到一个数字结尾，所以我们考虑以当前位结尾的最大连续字段和是多少，首先根据状态可以确定，我们一定需要加上当前的值，因为这是以当前数位结尾的，而不是到当前数字范围内的，现在考虑如果以前一个数字结尾的最大字段和为非负数，那么我们直接将当前的数字加上前面的字段和，因为这样会使答案更大，如果以前一个数字结尾的最大字段和为负数，那么我们就抛弃前面的值，只保留当前的数字，因为加上前面的字段，只会使我们的答案变得更小。最终不断算下去，得到结果。

这种方法求出了每一种情况下的最大连续字段和，每求出一位只会利用前面求出的值，并且不会改变前面的值，这就保证了无后效性。

那么，我们可以轻而易举的设置出动态规划的三要素。设$dp[i]$表示以$a[i]$结尾的最大字段和，这里再次强调，状态并不是指从第一个数到第$i$个数范围内的最大字段和。状态转移方程分为两种情况：

$$dp[i]=\begin{cases}dp[i-1]+a[i],&dp[i-1]\ge 0\\a[i],&dp[i-1]<0\end{cases}$$

对于上面的转移方程，还可以进行空间优化，只开$dp[]$数组就可以，因为原数据只会用一次。所以转移方程可以转化为：

$$dp[i]=\begin{cases}dp[i-1]+dp[i],&dp[i-1]\ge 0\\dp[i],&dp[i-1]<0\end{cases}$$

那么初始化就是$dp[i]=a[i]$（$a[i]$可省略），边界条件就是$n$的范围（这里的$n$指的是原序列的长度）。因为每个状态中储存着每一种情况的最大值，所以我们需要遍历一遍，求出$dp[]$数组中的最大值，即$\max\{dp[i]\}(i\in [1,n])$。

线性动态规划的扩展应用

这里主要是将线性的一维扩展到了多维，下面给出两个经典例题。

过河卒

先从最原始的问题开始，给出一张$n \times m$的图，每次只能能向下或者向右走，问从$(1,1)$走到$(n,m)$的方案书有多少种。

这个问题很简单，我们可以想到，走到一个点只有两种方法：从上方走下来或者从左方走过来（除非有边界），那么走到这个点的方案数就是从上方走下来到从左方走下来的方案数之和。

所以，我们设计$dp[i][j]$表示从起点走到$(i,j)$的方案数，转移方程即分有三种情况（考虑边界）：

$$dp[i]=\begin{cases}dp[i-1],&j=1\\dp[j-1],&i=1\\dp[i-1]+dp[j-1],&i\neq1,i\neq1\end{cases}$$

但是，这道题设置了障碍，有一只马在图中，使得图中至多有$9$个点不能经过，但只需要将上面的转移方程稍加修改，把不能经过的点也当作边界即可。由此，最终的答案就是$dp[n][m]$。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<bits/stdc++.h>
long long a[10010][10010];
using namespace std;
int main()
{
	int m,n,j,i;
	cin>>m>>n>>j>>i;
	a[10][10]=1;
	a[j+10][i+10]=a[j+2+10][i-1+10]=a[j+2+10][i+1+10]=a[j-2+10][i+1+10]=a[j-2+10][i-1+10]=a[j+1+10][i-2+10]=a[j+1+10][i+2+10]=a[j-1+10][i+2+10]=a[j-1+10][i-2+10]=-1;
	for(int x=10;x<=m+10;x++)
	{
		for(int y=10;y<=n+10;y++)
		{
			if(a[x][y]==1)
				continue;
			if(a[x][y]==-1)
				continue;
			if(a[x-1][y]==-1&&a[x][y-1]!=-1)
				a[x][y]=a[x][y-1];
			if(a[x][y-1]==-1&&a[x-1][y]!=-1)
				a[x][y]=a[x-1][y];
			if(a[x-1][y]!=-1&&a[x][y-1]!=-1)
				a[x][y]=a[x-1][y]+a[x][y-1];
		}
	}
	cout<<a[m+10][n+10];
 return 0;
}

数字三角形

数字三角形可以看作是一个简化版的过河卒，但是思想有所变动，为了使这一道题的判断尽可能地少，我们可以倒推，从下往上选择更大的数字累加，最终顶端的数字就是结果。

状态、转移方程基本一致，不多叙述。

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define N 1000100
int dp[1001][1001],ans,r,a[1001][1001];
int main()
{
	scanf("%d",&r);
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i-1][j-1]+a[i][j]);
		}
	for(int i=1;i<=r;i++)
	{
		ans=max(ans,dp[r][i]);
	}
	printf("%d",ans);
	return 0;
}

线性动态规划的进阶应用

P4158 [SCOI2009]粉刷匠

来源：洛谷：P4158 [SCOI2009]粉刷匠

首先观察问题，共有$n$块木板，每一块木板又$m$个格子，也就是说相当是一个$n\times m$图被切成了好$n$个$1 \times m$条。不同木板之间没有直接的关系。每一次粉刷都是一个连续的区间，一共只能粉刷$T$次，每次粉刷红色和蓝色，如果与要求粉刷的颜色不同或者没有被粉刷，就算做错误粉刷，反之就是正确的粉刷。且每个格子只能刷一次。

直接通过题干可以得出结论，每个木板都要刷上颜色，因为无论是刷错颜色还是不刷都会按照错误粉刷处理，然而刷上颜色又会有正确粉刷的可能性，所以每个格子都要粉刷。然后就去分析所有格子都刷的情况。

假设一块板子前面的格子都已经刷好了颜色，我们就需要考虑以下的问题：

  1. 前面的格子是否刷错了颜色
  2. 我要不要改变当前刷子的颜色
  3. 当前格子与前面的格子的颜色是否相同

合并以上问题整理一下。

  • 如果前面的格子刷错了颜色、前面的格子与当前格子的颜色不同，那么我们就可以选择不换刷子刷下去，此时这个格子的颜色是正确的；也可以换刷子颜色，此时这个格子的颜色是错误的。
  • 如果前面的格子刷错了颜色、前面的格子与当前各自的颜色相同，那么我们就可以选择不换刷子刷下去，此时这个格子的颜色是错误的；也可以换刷子颜色，此时这个格子的颜色是正确的。
  • 如果前面的格子刷对了颜色、前面的格子与当前格子的颜色不同，那么我们就可以选择不换刷子刷下去，此时这个格子的颜色时错误的；也可以换刷子颜色，此时这个格子的颜色时正确的。
  • 如果前面的格子刷对了颜色、前面的格子与当前格子的颜色相同，那么我们就可以选择不换刷子刷下去，此时这个格子的颜色时正确的；也可以换刷子颜色，此时这个格子的颜色时错误的。

除了这四种刷板子内部的情况，我们还需要考虑当刷每一块板子第一个位置的转移情况：

  • 无论如何，当我们刷到第二块板子时都需要换一次刷子。
  • 换刷子的时候可以选择与当前格子颜色不同的颜色，也可以选择与当前格子颜色相同的颜色。
  • 无论换成什么颜色，我们都可以由上一块板子最后一个位置转移过来。此时上一块板子可以是刷错颜色的，也可以是刷对颜色的。

现在，所有的转移都考虑清楚了，再考虑我们应该什么从时候转移过来。因为我们在刷一块板子时，我们不一定刷到第几次，所以需要从之前刷过的所有情况的答案转移过来。

至此，我们解决了阶段问题，状态可以设计出来：设$dp[i][j][k][0/1]$，$i$表示现在刷第$i$块板子，$j$表示第$i$块板子的第$j$个位置，$k$表示从开始到现在一共换了多少次刷子，$0/1$表示这一块板子刷错/刷对的结果，转移方程根据上面的分析可以列出来：

$$dp[i][j][k][p]=\begin{cases}\max\{dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]\},&j=1,p=0\\\max\{dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]\}+1,&j=1,p=1\\\max\{dp[i][j-1][k][1],dp[i][j-1][k-1][0]\},&j\neq1,p=0,a[i][j]\neq a[i][j-1]\\\max\{dp[i][j-1][k][0],dp[i][j-1][k-1][1]\}+1,&j\neq1,p=1,a[i][j]\neq a[i][j-1]\\\max\{dp[i][j-1][k][0],dp[i-1][j-1][k-1][1]\},&j\neq 1,p=0,a[i][j]=a[i][j-1]\\\max\{dp[i][j-1][k][1],dp[i-1][j-1][k-1][0]\}+1,&j\neq1,p=1,a[i][j]=a[i][j-1]\end{cases}$$

最终答案就是$\max\{dp[n][m][t][0],dp[n][m][t][1]\}$。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long uLL;
typedef __int128 int128;
typedef unsigned __int128 uint128;
typedef long double Ld;
#define reg register;
#define space putchar(' ')
#define enter putchar('\n')
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 1000010
namespace Fast{
	template<typename T>inline void read(T &x){
		x=0;bool f=false;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(f)x=~x+1;
	}
	template<typename T>inline void print(T x){
		int s[65],top=0;
		if(x<0)putchar('-'),x=~x+1;
		while(x)s[++top]=x%10,x/=10;
		if(!top)s[++top]=0;
		while(top)putchar(s[top--]+'0');
	}
	template<typename T,typename...Args>inline void read(T &x,Args&...others){
		read(x),read(others...);
	}
	template<typename T,typename...Args>inline void print(T x,Args...others){
		print(x),space,print(others...);
	}
	const double eps=1e-7;
	template<typename T>inline T Abs(T x){return x>0?x:-x;}
	template<typename T>inline T Max(T x,T y){return x>y?x:y;}
	template<typename T>inline T Min(T x,T y){return x<y?x:y;}
	template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
	template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
	template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
	template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
	template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;
int a[55][55];
int dp[55][55][2501][2],n,ans,m,t;
int main()
{
	read(n,m,t);
	for(int i=1;i<=n;i++){
		char c[55];
		scanf("%s",c+1);
		for(int j=1;j<=m;j++){
			a[i][j]=c[j]-'0';
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=t;k++){
				if(j==1){
					dp[i][j][k][0]=max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]);
					dp[i][j][k][1]=max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0])+1;
				}
				else
					if(a[i][j]!=a[i][j-1]){
						dp[i][j][k][0]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]);
						dp[i][j][k][1]=max(dp[i][j-1][k][0],dp[i][j-1][k-1][1])+1;
					}
					else{
						dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k-1][1]);
						dp[i][j][k][1]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0])+1;
					}
			}
		}
	}
	ans=max(dp[n][m][t][0],dp[n][m][t][1]);
	print(ans);
	return 0;
}

（代码可能存在错误，数据很水，过去写过多次，每次故意写错一处，最终结果均为AC）

文章标题：线性动态规划
文章链接：https://www.laoguantx.top/%e7%ba%bf%e6%80%a7%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92.html
文章内容仅供参考，其中可能会有部分内容参考、引用其他网站，转发请务必标注作者为 “老官童鞋gogo” ，原文链接为 https://www.laoguantx.top/%e7%ba%bf%e6%80%a7%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92.html 。
动态规划（DP）
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
动态规划

							
							

							
分治

							
							

							
计算机及OI发展史

							
							

							
树链剖分

							
							

							
P3528 [POI2011]PAT-Sticks 题解