目录
前言：
背景知识：
正文：
什么是动态规划（更新中）：
理解动态规划：
状态：
状态转移：
运用动态规划（分析步骤）：
例题集（时间顺序）
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：最长公共子序列
10.蓝桥OJ 3349：可构造的序列总数（二维DP）
11.蓝桥OJ 3349：最快洗车时间（二维DP）
前言：
算法学习记录不是算法介绍，本文记录的是从零开始的学习过程（见到的例题，代码的理解……），所有内容按学习顺序更新，而且不保证正确，如有错误，请帮助指出。
学习工具：蓝桥OJ，LeetCode
背景知识：
你已经了解过DFS。
（算法学习记录：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;
}10.蓝桥OJ 3349：可构造的序列总数（二维DP）
dp[i][j]表示在位置i处以数字j结尾的序列总数。
发现，dp[i][?]处的上一步一定是dp[i-1][?]
现讨论 j 的取值：
对于每一个 j ，遍历每一个小于 j 的数，得到两个因子，
因为题目中的倍数限制，所以上一步一定是有这两个因子的情况。（完全平方单独讨论）
状态转移方程：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4000;
const ll mod = 1e9+7;
int n, k;
ll dp[N][N], two[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> k >> n;
for(int i = 1; i <= k; ++ i)
{
dp[1][i] = 1;
}
if(n == 1)
{
cout << k;
return 0;
}
for(int i = 2; i <= n; ++ i)
{
for(int j = 1; j <= k; ++ j)
{
for(int t = 1; t * t <= j; ++ t)
// 这里的优化是关键，如果直接枚举从1到j会 t， 而对每一个小于根号j的因数当你找出他的时候就能找到一个对应的大于根号j的因数 因此时间复杂度从O(n3)优化到O(n2 * 根号n） 大概2e8 极限能过
{
if(t * t == j) dp[i][j] = (dp[i][j] + dp[i-1][t]) % mod;
else if(j % t == 0) dp[i][j] = (dp[i][j] + dp[i-1][t] + dp[i-1][j/t]) % mod;
}
}
}
ll ans = 0;
for(int i = 1; i <= k; ++ i) ans = (ans + dp[n][i]) % mod;
cout << ans;
return 0;
}11.蓝桥OJ 3349：最快洗车时间（二维DP）
这题很容易想到用贪心的思想解决，但是这无法保证两个地方时间尽可能的相近。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;cin >> n;
vector<int>a(n);
for(int k = 0;k < n;k ++)cin >> a[k];
//sort(a.begin(),a.end());
for(int l = n - 1;l >= 0;l--){
for(int x = 0;x < l;x ++)
{
if(a[x+1] < a[x])swap(a[x+1],a[x]);
}
}
int suma=0;
int sumb=0;
int i=0,j=n-1;
while(i!=j)
{
sumb+=a[j];
j--;
while(suma<sumb)
{
suma+=a[i];
if(i==j)break;
i++;
}
}
cout << max(suma,sumb) << endl;
return 0;
}考虑这个反例：
因此只能使用动态规划枚举所有可能：文章来源：https://www.toymoban.com/news/detail-822360.html
正解：文章来源地址https://www.toymoban.com/news/detail-822360.html
//本题的难点仍在于状态转移方程的设计与列写
//由于两台机器完全相同，若总时间为sum，其中一台洗车时间为i，则另一台洗车时间为sum-i
//i与sum-i中的较大值即为最终答案
//故本题可以只考虑其中一台机器，枚举其所有洗车方案(可能花费的洗车时间)并使用动态规划验证该方案是否可行
//最终遍历该台机器所有可行的洗车方案，计算并比较出最终的洗车时间
//注：本题有一种错误解法，即把数组排序以后令两台机器分别从头和尾开始往中间遍历洗车
//这种解法是基于贪心思想的，但它并不能保证两台机器的洗车时间尽可能的接近，因此无法得出正确答案
//事实上在允许的时间复杂度内，本题并不存在直接找出最佳洗车方案的算法，
//只能使用动态规划来验证每一种洗车方案,然后比较得出最终答案
#include <bits/stdc++.h>
using namespace std;
int Time[109];
bool dp[109][10009];
//dp[i][j]表示只考虑前i辆车(每辆车可能洗或不洗)，能否使总洗车时间为j，若能则为true
int main()
{
int N;
int sum=0;
int ans=1e9;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>Time[i];
sum=sum+Time[i];//计算总洗车时间
}
for(int i=0;i<=N;i++)dp[i][0]=true;//初始化，若该机器总洗车时间为0，必然能做到
for(int i=1;i<=N;i++)//遍历每一种可能的洗车方案，依次考虑前1~N辆车
{
for(int j=0;j<=sum;j++)//对于每一种洗车方案，遍历该机器所有可能的洗车时间，可能花0~sum分钟
{
//若洗前i-1辆车的时间为j-Time[i],则洗前i辆车的时间可以是j(洗第i辆车)
//若洗前i-1辆车的时间为j，则洗前i辆车的时间也可以是j(不洗第i辆车)
//两种情况满足其一，dp[i][j]即为true
//此处注意j-Time[i]要大于等于0，故分开写(合在一起写会有一个测试点错误)
dp[i][j]=dp[i-1][j];
if(j>=Time[i])dp[i][j]=dp[i][j] | dp[ i - 1 ][ j - Time[i] ];
}
}
for(int i=1;i<=sum;i++)//遍历其中一台机器所有可能的洗车时间1~sum
{
if(dp[N][i])//若对于前N辆车，该机器洗车时间可以是i
{
int tmp=max(sum-i,i);//则对于该洗车方案，两台机器洗车完成的时间是sum-i和i之间的较大值
if(tmp<ans)ans=tmp;//比较得出所有洗车方案所花时间的最小值
}
}
cout<<ans<<endl;
return 0;
}到了这里，关于算法学习记录：动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
