算法学习记录：动态规划

目录

前言：

背景知识：

正文：

?什么是动态规划（更新中）：

?理解动态规划：

状态：

状态转移：

?运用动态规划（分析步骤）：

例题集（时间顺序）?

1.蓝桥OJ 3820：混境之地5（DFS）

2.蓝桥OJ 216：地宫取宝（DFS）

3.蓝桥OJ 1536：数字三角形（迭代法）

4.蓝桥OJ 3367：破损的楼梯（迭代法）

5.蓝桥OJ 3423：安全序列（迭代法）

6.蓝桥OJ 389：摆花（二维DP）（迭代法）

7.蓝桥OJ 3362：建造房屋（二维DP）（迭代法）

8.最长上升子序列（LIS）

蓝桥OJ 1358：蓝桥勇士

蓝桥OJ 742：合唱队形

9.最长子序列（LCS）

蓝桥OJ 1189：最长公共子序列

---

前言：

? 算法学习记录不是算法介绍，本文记录的是从零开始的学习过程（见到的例题，代码的理解……），所有内容按学习顺序更新，而且不保证正确，如有错误，请帮助指出。

学习工具：蓝桥OJ，LeetCode

背景知识：

你已经了解过DFS。

正文：

?什么是动态规划（更新中）：

全称”Dynamic Programing“，是将复杂问题分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。

关系：

?图中认为（递归+记忆化）属于动态规划，这个不完全正确：

动态规划一个明显的特征是它涉及求最值：

它与DFS的不同点：

相同点：

?理解动态规划：

可以通过用记忆化DFS求解斐波那契问题，来理解动态规划中的状态转移。

DFS + 记忆化 的算法学习记录

状态：

形如dp[i][j] = val 的取值，用于描述、确定状态所需的变量

状态转移：

状态与状态的转移关系，一般可以表示为一个数学表达式，转移的方向决定迭代或递归的方向。

?运用动态规划（分析步骤）：

1.确定状态，题目关键词”到第i个为止、xx为j（xx为k）的方案数/最小代价/最大价值……“

2.确定状态转移方程，从已知状态得到新状态的方法

3.根据状态转移的方向决定使用迭代法还是递归法（记忆化）

例题集（时间顺序）?

1.蓝桥OJ 3820：混境之地5（DFS）

dp[x][y][t]表示从起点到点(x,y)，且喷气背包使用了t次的?状态?下是否可以到终点。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const int inf = 1e9,N = 1e3 + 3;
 
int n,m,k,sx,sy,fx,fy,h[N][N];
 
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
bool inmp(int x,int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
//返回值表示能否到达终点(fx,fy),t表示当前使用的喷气背包的次数
 
bool dfs(int x,int y,int t)
{
	if(x == fx && y == fy)return true;
	
	for(int i = 0;i < 4 ;i ++)
	{
		int nx = x + dx[i],ny = y + dy[i];
		
		if(!inmp(nx,ny))continue;
		
		if(!t)
		{
			//不用
			if(h[x][y] > h[nx][ny] && dfs(nx,ny,0))return true;
			
			if(h[x][y] + k > h[nx][ny] && dfs(nx,ny,1))return true;
		}else
		{
			if(h[x][y] > h[nx][ny] && dfs(nx,ny,1))return true;
		}
	}
	return false;
}
 
int main()
{
	cin >> n >> m >> k;
	cin >> sx >> sy >> fx >> fy;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++)
		{
			cin >> h[i][j];
		}
	}
	
	cout << (dfs(sx,sy,0)?"Yes" : "No") << '\n';
	return 0;
}

2.蓝桥OJ 216：地宫取宝（DFS）

设置状态：dp[x][y][mx][cnt]表示走到(x,y)，手中cnt个宝，且最大值为mx的方案

注意：开dp数组时要估算大小，这个四维数组占用空间约1e6，已经接近上限。

#include<bits/stdc++.h>
using namespace std;
 
using ll = long long ;
const ll p = 1e9 + 7;
const int inf = 1e9 ,N = 55;
 
int n,m,k,c[N][N];
 
int dx[] = {0,1};
int dy[] = {1,0};
 
 
int dp[N][N][15][15]; 
 
bool inmp(int x,int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
ll dfs(int x,int y,int mx, int cnt)
{
	if( x == n && y == m )return (ll)(cnt == k);
	if(dp[x][y][mx][cnt] != -1)return dp[x][y][mx][cnt];
	
	ll res = 0;
	
	for(int i = 0;i < 2;i ++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		
		if(!inmp(nx,ny))continue;
		
		//拿上这个宝贝
		if(c[nx][ny] > mx && cnt < k)res = (res + dfs(nx,ny,c[nx][ny],cnt + 1)) % p;
		
		//不拿这个宝贝
		res = (res + dfs(nx,ny,mx,cnt)) % p;
		
	}
	return dp[x][y][mx][cnt] = res;
}
 
int main()
{
	memset(dp,-1,sizeof dp);
	cin >> n >> m >> k;
	
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++)
		{
			cin >> c[i][j];
			c[i][j] ++;   //整体加1不影响结果，这样对mx可以设置初值为0，避免数组越界到-1
		}
	}
	cout << (dfs(1,1,0,0) + dfs(1,1,c[1][1],1)) % p;
	
	return 0;
}

3.蓝桥OJ 1536：数字三角形（迭代法）

方案一（未通过）：

设状态dp[i][j]表示从第i行第j列的元素往下走的所有路径当中最大的和

状态转移方程：dp[ i ][ j ] = max( dp [ i + 1 ][ j ] ,dp[ i + 1 ][ j + 1 ] )

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105;
ll a[N][N],dp[N][N];

int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i ++)
	    for(int j = 1;j <= i; ++ j)cin >> a[i][j];
	
	for(int i = n;i >= 1; --i)
		for(int j = 1;j <= i; ++j){
		dp[i][j] = a[i][j] + max(dp[i + 1][j],dp[i + 1][j + 1]);
	}
	cout << dp[1][1] << endl;
	return 0;
}

?方案二（可行）：

思路一的问题是没有考虑题中条件：“次数相差不能超过1”

为了解决这个问题，考虑次数相差符合要求的解的特征：

1.若最后一行奇数个元素：只有中间那个作出口才行

2.若最后一行偶数个元素：中间两个作出口都有可能

还要考虑取最大值，因此：

设置状态A[i][j]表示顶点到该位置路程最大值

状态转移方程：A[ i ][ j ] = A[ i?][ j ]?+ max( A[ i -?1 ][ j - 1?] , A[ i -?1 ][ j ] )

#include<bits/stdc++.h>
using namespace std;
int Max(int a,int b){//返回a，b的最大值 

	return (a>b?a : b);
}
int main() 
{
	int n;
	cin >> n;
	int An[n][n];//储存三角形每个位置的值 
	
	for(int i = 0; i < n; i ++)//三角形的行i的循环 
	{
		for(int j = 0; j < i + 1; j ++)//三角形列j的循环，列最大等于该行的行数 
		{
			scanf("%d", &An[i][j]);
		}
	}
	for(int i = 0; i < n; i ++)//三角形的行i的循环 
	{
		for(int j = 0; j < i + 1; j ++)//三角形列j的循环，列最大等于该行的行数 
		{
			if(i >= 1)//不是第一列只有一个数的情况下 
			{
				if(j == 0)//数组第一列没有左上角的值，直接加上面的值就是最大值 
					An[i][j] += An[i -1][j];
				else if(j == i)//即数组每列最后一个没有正上方的值，直接加左上值即可 
					An[i][j] += An[i - 1][j - 1];
				else//其余情况加其左上右上的最大值 
				{
					int max1 =Max(An[i - 1][j - 1],An[i - 1][j]); 
					An[i][j] += max1;
				}
			}
		}
	}
	//上面执行完后，An数组每个值表示顶点到该位置路程最大值
	//向左下走的次数与向右下走的次数相差不能超过 1,即输出第n行最中间二个的最大值
	//注意分行数的奇偶
	if(n%2==1)  
		printf("%d\n",An[n-1][(n-1)/2]);
	else 
		printf("%d\n",Max(An[n-1][(n-1)/2],An[n-1][(n-1)/2+1]));
	
	return 0;
}

4.蓝桥OJ 3367：破损的楼梯（迭代法）

这个题使用一种递推的思路：

对于每一个要到的楼梯：

求到这里有几种方案，

就考虑到这个位置的前一步：从上一格位置A来 或 从上两格的位置B来

发现，无论从A还是B来，都分别只有一种方案

所以，归纳出规律：方案数（位置n） = 方案数（位置n-1）+ 方案数（位置n - 2）

由此得到状态转移方程：????dp[i]?=?(dp[i?-?1]?+?dp[i?-?2])?%?p;

#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
const int N = 1e5 + 9;
const ll p = 1e9 + 7;
ll dp[N];

bool broken[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin >> n >> m;
	
	for(int i = 1;i <= m;i ++){
		int  x;cin >> x;
		broken[x] = true;
	}
	
	dp[0] = 1;
	if(!broken[1])dp[1] = 1;
	for(int i = 2;i <= n; ++i)
	{
		if(broken[i])continue;
		dp[i] = (dp[i - 1] + dp[i - 2]) % p;
	}
	
	cout << dp[n] << endl;
	
	return 0;
}

5.蓝桥OJ 3423：安全序列（迭代法）

这题与上一题类似但有不同：

考虑有n个位置的总方案数，位置n可以有桶可以没桶，每一个位置都可以有桶或没桶

把问题划分为从第几个位置开始没桶的n种情况? （不重不漏）

所以方案总数 == 方案数（第一个位置开始没桶）+ 方案数（第二个位置开始没桶）+ 方案数（第三个位置开始没桶）+ ……+方案数（第n个位置开始没桶）

再考虑怎么求从第 i 个位置开始没桶（位置 i 摆最后的桶）的方案数：

发现既然这个位置有了桶，因为要间隔k，这个位置 - k 之前的每一个位置有桶，

下一步都可以到当前状态，问题被进一步划分。

归纳出规律：该方案数 == 起始位置到这个位置前k个位置开始没桶的情况的方案数之和

设置状态dp[i]表示以位置i结尾的方案总数，

归纳出状态转移方程：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9,p = 1e9 + 7;

ll dp[N],prefix[N];

int main()
{
	int n,k;cin >> n >> k;
	dp[0] = prefix[0] = 1;  //可能存在全都不放的情况
	for(int i = 1;i <= n;i ++)
	{
		if(i - k - 1 < 1)dp[i] = 1;
		else dp[i] = prefix[i - k - 1];
		prefix[i] = (prefix[i - 1] + dp[i]) % p;
	}
	cout << prefix[n] << endl;
	return 0;
}

6.蓝桥OJ 389：摆花（二维DP）（迭代法）

对于每一个到达一个位置并种了某种花的情况，

方案数都是先种上一个位置并种了少用一种花的方案数，

具体来说：

这个方案数就是：保持种到相同位置，这最后一种花种了多少盆的所有情况的方案数之和

设状态dp[i][j]表示到第i种花为止（不一定以第i种花结尾），到第j个位置（1-j都放了花）的情况下的总方案数：

图解：

归纳出状态转移方程：

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
using ll = long long;
const ll p = 1e6 + 7;
ll a[N],dp[N][N];

int main()
{
	int n,m; cin >> n >> m;
	for(int i = 1;i <= n; i ++)cin >> a[i];
	
	dp[0][0] = 1;
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 0;j <= m;j ++)
		{
			for(int k = 0;k <= a[i] && k <= j; k ++){
				dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

7.蓝桥OJ 3362：建造房屋（二维DP）（迭代法）

#include <iostream>
using namespace std;
using ll=long long;
const ll M=1e9+7;
const int N=1000;
ll dp[N][N]; //dp[j][k]表示截至到第j行，第k个房子的方案数
int main()
{
	int n,m,k;cin>>n>>m>>k;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			for(int s=1;s<=m&&s<=j-i+1;s++)
				dp[i][j]=(dp[i-1][j-s]+dp[i][j])%M;
		}
	}
	ll ans=0;
	for(int i=1;i<=k;i++)
		ans+=dp[n][i];
	cout<<(ans)%M;
	return 0;
}

?8.最长上升子序列（LIS）

?LIS（Longest Increasing Subsequence最长上升子序列）是一个经典的DP模型

朴素LIS模型：时间复杂度O（n^2）

二分LIS模型：时间复杂度O（nlogn）

?LIS指一个序列中，按照原顺序选出若干个不一定连续的元素组成的序列，要求序列递增

求解：

设dp[i]表示1~i中以a[i]结尾的最长上升子序列的长度

状态转移方程：

图解：

蓝桥OJ 1358：蓝桥勇士

状态转移方程：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 9;
int a[N],dp[N];

int main()
{
    int n ;cin >> n;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	
	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);
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++)ans = max(ans,dp[i]);
	cout << ans << endl;
	return 0;
}

蓝桥OJ 742：合唱队形

设状态dpl[i]表示1~i的最长上升子序列的长度，dpr[i]表示反向的n~i的最长上升子序列的长度，求出两个dp数组后，计算出最大的 dpl[i] + dpr[i] - 1 即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int N = 150;
int a[N],dpl[N],dpr[N];

int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n; ++i)cin >> a[i];
	for(int i = 1;i <= n;i ++)
	{
		dpl[i] = 1;
		for(int j = 1;j < i;j ++)if(a[i] > a[j])dpl[i] = max(dpl[i],dpl[j] + 1);
	}
	for(int i = n;i >= 1;--i)
	{
		dpr[i] = 1;
		for(int j = i + 1;j <= n;j ++)if(a[i] > a[j])dpr[i] = max(dpr[i],dpr[j] + 1);
	}
	
	int ans = n;
	for(int i = 1;i <= n;i ++)ans = min(ans,n - (dpl[i] + dpr[i] - 1));
	
	cout << ans << endl;
	return 0;
}

9.最长子序列（LCS）

LCS（Longest Common Subsequence 最长公共子序列）是一个经典的DP模型。

复杂度：O（n^2）

LCS问题是给定两个序列A和B，求它们的最长公共子序列。

求解：设dp[i][j]表示A[1~i]序列和B[1~j]序列中的最长公共子序列长度。

蓝桥OJ 1189：最长公共子序列

状态转移方程：

解释：

当a[i] == b[i]，将它们插入到LCS后面，使长度变长1

当a[i]!=b[i]，说明此时LCS不会变成，就要从dp[i-1][j]和dp[i][j-1]取大

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int n,m,a[N],b[N],dp[N][N];
int main(){
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	for(int i = 1;i <= m;i ++)cin >> b[i];
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= m;j ++)
		{
			if(a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}

另：求出其中一个最长的子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int n,m,a[N],b[N],dp[N][N];
int main(){
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	for(int i = 1;i <= m;i ++)cin >> b[i];
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= m;j ++)
		{
			if(a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}