算法学习记录：动态规划基础

目录

前言：

背景知识：

正文：

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

 理解动态规划：

状态：

状态转移：

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

例题集（时间顺序） 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

using namespace std;

int main()

{

int n;cin >> n;

vectora(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

{

suma+=a[i];

if(i==j)break;

i++;

}

}

cout << max(suma,sumb) << endl;

return 0;

}

考虑这个反例：

因此只能使用动态规划枚举所有可能：

正解：

//本题的难点仍在于状态转移方程的设计与列写

//由于两台机器完全相同，若总时间为sum，其中一台洗车时间为i，则另一台洗车时间为sum-i

//i与sum-i中的较大值即为最终答案

//故本题可以只考虑其中一台机器，枚举其所有洗车方案(可能花费的洗车时间)并使用动态规划验证该方案是否可行

//最终遍历该台机器所有可行的洗车方案，计算并比较出最终的洗车时间

//注：本题有一种错误解法，即把数组排序以后令两台机器分别从头和尾开始往中间遍历洗车

//这种解法是基于贪心思想的，但它并不能保证两台机器的洗车时间尽可能的接近，因此无法得出正确答案

//事实上在允许的时间复杂度内，本题并不存在直接找出最佳洗车方案的算法，

//只能使用动态规划来验证每一种洗车方案,然后比较得出最终答案

#include

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

}

}

cout<

return 0;

}

文章链接

 您阅读本篇文章共花了：