复试机试算法总结#11：动态规划

98 阅读 0 评论 65 点赞

我是靠谱客的博主现代树叶，最近开发中收集的这篇文章主要介绍复试机试算法总结#11：动态规划，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 递推求解

2. 最大连续子序列和

2.1 一维情况

2.2 二维情况：最大子矩阵

3. 最长递增子序列LIS

4. 最长公共子序列LCS

5. 背包问题

5.1 0-1背包

5.2 完全背包

5.3 多重背包

1. 递推求解

保存中间结果，在后面的计算中可直接调用，避免重复计算耗时。关键是找到数列的递推关系。

例题：N阶楼梯上楼问题

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=91;
long long dp[MAXN];
int main()
{
//初始化
dp[0]=0;
dp[1]=1;
int n;
for(int i=2;i<MAXN;++i)
{
dp[i]=dp[i-1]+dp[i-2];//迈最后一步时，只可能是一级台阶或两级台阶
}
while(cin>>n)
{
cout<<dp[n+1]<<endl;
}
return 0;
}

2. 最大连续子序列和

2.1 一维情况

设置数组dp[ ]，dp[i]表示以序列元素A[i]为末尾的连续序列的最大和。最终，最大连续子序列和便是dp数组中的最大值。

只存在两种情况：

最大和的连续序列中只有一个元素，即A[i]自身，所以dp[i]=A[i]
最大和的连续序列中有多个元素，即dp[i]=A[j]+...+A[i-1]+A[i]。那么就有dp[i-1]=A[j]+...+A[i-1]。所以dp[i]=dp[i-1]+A[i]

由此可得状态转移方程：dp[i] = max{A[i], dp[i-1] + A[i] }。输出dp中的最大值就能得到最大连续子序列和。

例题：最大序列和

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000000;
long long dp[MAXN];
long long a[MAXN];
long long MaxSubsequence(int n)
{
long long answer=0;
for(int i=0;i<n;++i)
{
if(i==0)
dp[i]=a[i];
else
dp[i]=max(a[i],dp[i-1]+a[i]);
answer=max(answer,dp[i]);
}
return answer;
}
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;++i)
cin>>a[i];
long long answer=MaxSubsequence(n);
cout<<answer<<endl;
}
return 0;
}

2.2 二维情况：最大子矩阵

设最大子矩阵上下边分别为i行和j行，则有两种情况：

i = j 时，最大子矩阵和就变成了最脆大连续子序列
i != j 时，把从i到j行得元素累加，得到一个一维数组，其最大连续子序列就是最大子矩阵和

例题：最大子矩阵

本题中在i!=j时，可不必对原始矩阵进行累加，而是再设一二维的辅助矩阵从上至下进行累加，一维数组则由其进行减行即可得到

3. 最长递增子序列LIS

从一个已知的序列中，取出若干元素（不必连续），保持它们在原序列中的相对顺序，且这些元素大小递增。最长递增子序列即为所有可能的子序列中最长的那个。

求解：首先设置数组dp[ ]，用dp[i]表示以A[i]作为末尾的LIS的长度。于是，dp中的最大值即为最长递增子序列的长度。且只有两种情况：

A[i]之前的元素都比它大，即最长递增子序列只有A[i]一个元素。所以dp[i]=1。
A[i]之前的元素A[j]比它小，此时只需把A[i]添加到以A[j]为末尾的LIS，即可得到新的LIS。可得dp[i]=dp[j]+1。所以把i之前的元素逐一遍历便可得到以A[i]为末尾的LIS长度dp[i]。

由两种情况可得状态转移方程：dp[i]=max{ 1, dp[j] + 1 | j < i && Aj < Ai }。

例题：拦截导弹

//状态转移方程为dp[i]=max{1,dp[j]+1|j<i&&Aj>=Ai}，不递减就行
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=25;
int height[MAXN];
int dp[MAXN];
int main()
{
int k
while(cin>>k)
{
for(int i=0;i<k;++i)
cin>>height[i];
int answer=0;
for(int i=0;i<k;++i)
{
dp[i]=1;//情况1，初始化为1
for(int j=0;j<i;++j)//遍历i之前的元素
{
if(height[i]<=height[j])
dp[i]=max{dp[i],dp[j]+1};
}
answer=max(answer,dp[i]);//更新最大值
}
cout<<answer<<endl;
}
return 0;
}

4. 最长公共子序列LCS

给定两个字符串S1，S2（字符数组），求字符串S3，它同时为S1和S2的子串（不必连续），且要求长度最长。

求解：设置二维数组dp[ ][ ]，令dp[i][j]表示以S1[i]和S2[j]作为末尾的LCS的长度。只需依次遍历i和j就能得到各个dp[i][j]，而LCS的长度即为dp[n][m]。两种情况如下：

S1[i] = S2[j]：则此时必存在一个最长公共子串以S1[i]和S2[j]结尾，且比dp[i-1][j-1]多1。即dp[i][j]=dp[i-1][j-1]+1。
S1[i] != S2[j]：此时以S1[i-1]和S2[j]为结尾的子串、以S1[i]和S2[j-1]为结尾的子串两者中较大者为LCS的长度。所以此时有dp[i][j]=max{dp[i-1][j],dp[i][j-1]}。

可得状态转移方程：

dp[i][j] = dp[i-1][j-1]+1 S1[i] = S2[j]
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] } S1[i] != S2[j]

关于边界值：若两个子串中有一个为空，那LCS长度必为0，则有：

dp[i][0]=0 (0<=i<=n)
dp[0][j]=0 (0<=j<=m)

注：字符串最好从下标1而非0开始输入，有利于处理边界和初始化

例题：Coincidence

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1001;
char s1[MAXN];
char s2[MAXN];
int dp[MAXN][MAXN];
int main()
{
while(cin>>s1+1>>s2+1)//从下标1开始输入
{
int n=strlen(s1+1);
int m=strlen(s2+1);
for(int i=0;i<=n;++i)
{
for(int j=0;j<=m;++j)
{
if(i==0||j==0)//处理边界值
{
dp[i][j]=0;
continue;
}
if(s1[i]==s2[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;
}

5. 背包问题

5.1 0-1背包

有n件物品，每件重量为w[i]，价值为v[i]，现有容量为m的背包，求如何选择物品使得装入背包的价值最大（每样物品仅一件）。求解：设一二维数组dp[ ][ ]，令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值。那么dp[n][m]的值就是问题的解。

对于第i件物品，分为放入和不放入两种情况：

对于容量为j的背包，若不放入第i件物品，则问题变成把前i-1件物品装入j容量背包的问题。dp[i][j] = dp[i-1][j]。
对于容量为j的背包，若放入第i件物品，那背包容量就变成j-w[i]，并且价值增加v[i]。则问题变为把前i-1件物品装入j-w[i]容量背包的问题。dp[i][j]=dp[i-1][ j - w[i] ] + v[i]。

得到状态转移方程：dp[i][j] = max( dp[i-1][j], dp[i-1][ j - w[i] ]+v[i] )

注：j-w[i]的值为负时不能进行状态转移

边界情况：装入0件物品和背包容量为0获得的价值都为0。

dp[i][0]=0 (0<=i<=n)
dp[0][j]=0 (0<=j<=m)

观察可知：dp[i][j]的转移仅与dp[i-1][j]和dp[i-1][ j - w[i] ]有关，即仅与二维数组中的上一行有关。那么可以把二维数组优化为一维数组，状态转移方程为：dp[j] = max( dp[j], dp[ j - w[i] ] + v[i] )。为保证正确的状态转移，必须保证更新中确定dp[j]时，dp[j-w[i]]尚未被本次更新修改。这就需要在每次更新时，倒序遍历所有j的值。

例题：点菜问题

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1001;
int w[MAXN];
int v[MAXN];
int dp[MAXN];
int main()
{
int n,m;//物品数 背包容量
cin>>n>>m;
for(int i=0;i<n;++i)
cin>>w[i]>>v[i];
for(int i=0;i<=m;++i)//初始化
dp[i]=0;
for(int i=0;i<n;++i)
{
for(int j=m;j>=w[i];--j)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
cout<<dp[m]<<endl;
return 0;
}

5.2 完全背包

与0-1背包问题的区别：每种物品都有无限个。

二维状态转移方程为：dp[i][j] = max( dp[i-1][j], dp[i][ j - w[i] ]+v[i] )。区别原因是放入第i个物品，后仍可再次放入第i个物品。

一维状态转移方程为：dp[j] = max( dp[j], dp[ j - w[i] ] + v[i] )。与0-1背包问题相同。但是在遍历j值时要正序遍历。

例题：Piggy-Bank

//此题求最小值，所以状态转移方程中用min
//此题要求恰好装满，那么初始化时要令dp[0]=0，且dp中其余值为无穷大
#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int MAXN=10000;
const int INF=INT_MAX;
int w[MAXN];
int v[MAXN];
int dp[MAXN];
int main()
{
int caseNumber;
cin>>caseNumber;
while(caseNumber--)
{
int e,f;//空罐的重量 满罐的重量
cin>>e>>f;
int m=f-e;//存钱罐容量
int n;//物品种类
cin>>n;
for(int i=0;i<n;++i)
cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)//初始化
dp[i]=INF;
dp[0]=0;
for(int i=0;i<n;++i)
{
for(int j=w[i];j<=m;++j)//正向遍历j
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
}
if(dp[m]==INF)
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<endl;
}
return 0;
}

5.3 多重背包

区别：每种物品最多只能取k件（每种物品数量为k[i]件）。

思路：同种物品被视为k种同重同价的不同物品，从而将问题转化为0-1背包问题。进而可以使用类似于快速幂的二进制拆分：将原数量为k的某种物品拆为若干组，每组整体视为一件物品，价值和重量为它们的总和。每组的物品个数为 $2^{0}$ ， $2^{1}$ ，...， $2^{c-1}$ ， k- $2^{c}$ +1，c是使k- $2^{c}$ +1≥0的最大整数。

例题：珍惜现在，感恩生活

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=10000;
int dp[MAXN];
int v[MAXN];//价格
int w[MAXN];//重量
int k[MAXN];//数量
int value[MAXN];//分解后物品价值
int weight[MAXN];//分解后物品重量
int main()
{
int caseNumber;
cin>>caseNumber;
while(caseNumber--)
{
int n,m;//物品数，容量
cin>>m>>n;
int number=0;//分解后物品数量
for(int i=0;i<n;++i)
{
cin>>w[i]>>v[i]>>k[i];
//分解
for(int j=1;j<=k[i];j<<1)
{
value[number]=j*v[i];
weight[number]=j*w[i];
number++;
k[i]-=j;
}
if(k[i]>0)
{
value[number]=k[i]*v[i];
weight[number]=k[i]*w[i];
number++;
}
}
for(int i=0;i<=m;++i)
dp[i]=0;
for(int i=0;i<number;++i)
{
for(int j=m;j>=weight[i];--j)
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
cout<<dp[m]<<endl;
}
return 0;
}

最后

以上就是现代树叶为你收集整理的复试机试算法总结#11：动态规划的全部内容，希望文章能够帮你解决复试机试算法总结#11：动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Other
浏览次数：98 次浏览
发布日期：2023-11-29 16:05:09
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_f3_14_z_18_y.html

复试机试算法总结#11：动态规划

概述

1. 递推求解

2. 最大连续子序列和

2.1 一维情况

2.2 二维情况：最大子矩阵

3. 最长递增子序列LIS

4. 最长公共子序列LCS

5. 背包问题

5.1 0-1背包

5.2 完全背包

5.3 多重背包

最后

评论列表共有 0 条评论

发表评论取消回复

复试机试算法总结#11：动态规划

概述

1. 递推求解

2. 最大连续子序列和

2.1 一维情况

2.2 二维情况：最大子矩阵

3. 最长递增子序列LIS

4. 最长公共子序列LCS

5. 背包问题

5.1 0-1背包

5.2 完全背包

5.3 多重背包

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复