动态规划大题解！！
2024-11-12 18:58:38
发布于：广东
动态规划大题解来啦！！
前言：
动态规划（dynamic programing（简称DP））通过记忆化的方式弥补了暴力搜索（如BFS，DFS等）重复计算某些区间的缺点。有的题目用动规甚至可以把时间复杂度从O(2^N) 降维打到O(N^2)。不过同时，这一算法也有一定门槛，是许多C++小白的一生之敌。
近期，我将会分两批，把ACGO官方的动规题单中的题目统一发放题解在一个帖子里面。这次的帖子是动规题单中相对简单的9道题（差不多占题单的50%）。
动规步骤
在正式开始之前，我需要说明做动态规划题目的步骤以及必须确定的及部分：
第一步：
众所周知，动规算法的主心骨是DP数组。但是与递推算法不一样的是，不一定所有的DP数组都自带答案。而如果不知道DP数组的含义而盲目去做只会导致越做越废（比如说那时的我）。所以做动规题目的第一步是确定该怎样定义DP数组 （也就是确定“DP[i][j]” 或 “DP[i]”的含义）。
第二步：
这一步是难倒大部分人的部分，也就是推导动态转移方程。听起来很高深，说白了就是当你有了前几项的答案，如何得出下一步的答案。其实有两种办法。1.（这一种很有用）打表+总结+AC。2.当你牛到了一定程度可以直接推导计算+AC。
第三步：
有的人万事俱备了，但是之后一通乱写，结果全部爆红。原因就是没有初始化好。怎样初始化呢？你可以把自己的大脑想成一个计算机，先自己推一下，把那些无法用转移方程推出来的找出来，它们就是初始化的对象。
第四步：
遍历顺序。这一点也是不可忽略的。比如像01背包和完全背包，遍历顺序完全是相反的（这一点也是和递推很不一样的一点）。具体该怎样要随机应变（反正很重要）。
第五步：
万事俱备，顺水推舟就行。
以上几点可能大家暂时体验不到，现在步入正题。来人！把准备的九道题搬出来，让他们体验一一下具体的五步！！
九道题的题解
1.A7927.兔子数列
本题个人认为反而更像递推，就是一道毫无争议的模板题。DP[n]就是本题答案。而且动态转移方程也告诉我们了。唯一要注意的就是初始化。从道理上来讲，应该初始化DP[1]和DP[2]。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int dp[100] = {0,1,1};//初始化1、2位
int main(){
int n;
cin >> n;
for(int i = 3;i <= n;i ++){
dp[i] = dp[i - 1] + dp[i - 2];//转移方程
}
cout << dp[n];
return 0;
}
但是，有人过了离开了，有人还在研究。这题还可以只用三个变量解决。具体逻辑大家自己理。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b = 1,c = 1;//a b为中介，c为答案
int n;
cin >> n;
if(n == 1 or n == 2){
cout << 1;
} else {
for(int i = 3;i <= n;i ++){
a = b;
b = c;
c = a + b;//往前挪一位并累加
}
cout << c;
}
return 0;
}
2.A7928.钞票问题
本题也是动规模板题。相信很多新手都是在这里死磕贪心挂掉的（忽略玩特判的）。动规做法的DP定义也很简单，DP[n]就是答案。但是在动态转移方程上面，就和递推有所不同了。他并不是通过前面一两位来获得后面的答案。这里就要展现记忆化搜索的强大之处了。由于我们是从前往后推的，因此DP数组当前位置的前面的所有位数已经知道了。而只有三种情况达到这个答案：1.i - 1加了一个1元的钞票变成i。2.i - 5加了一个5元的钞票变成i。3.i - 11 加了一个11元的钞票变成i。因此，只需要在DP[i - 1],DP[i - 5]和DP[i - 11]中找到最小值并+1就可以了（记得判边界）。
代码如下：
#include<bits/stdc++.h>
using namespace std;
vector<int> dp(2000005,1e9);
int main(){
dp[0] = 0;
int n;
cin >> n;
for(int i = 1;i <= n;i ++){
if(i - 5 >= 0) dp[i] = min(dp[i],1 + dp[i - 5]);//寻找最小的加一
if(i - 1 >= 0) dp[i] = min(dp[i],1 + dp[i - 1]);
if(i - 11 >= 0) dp[i] = min(dp[i],1 + dp[i - 11]);
}
cout << dp[n];
return 0;
}
3.A7929.不同的路径
这题不难，我们需要知道除了上边界以及左边界以外，对于每一个，要么从左边来，要么从上面来。所以DP[i][j] = DP[i - 1][j] + DP[i][j - 1]。对于上边界，只能从左边来；对于左边界，只能从上边来，所以全初始化为1。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long dp[105][105];
int main(){
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i ++) dp[i][0] = 1;//初始化左、上边界
for(int j = 0;j < m;j ++) dp[0][j] = 1;
for(int i = 1;i < n;i ++){
for(int j = 1;j < m;j ++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//动态转移方程
}
}
cout << dp[n - 1][m - 1];
return 0;
}
4.A627.数字三角形
题单里面没有这题，是我自己补进来的。（当然是因为它很重要）。其实这和上一题是一个循序渐进的过程。上题是求方案数，这题是求最大值（想到Dj了么）。是上方和左上方两个方位，用max来取最值。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main(){
int n,ans = 0;
cin >> n;
for(int i = 0;i < n;i ++){
for(int j = 0;j <= i;j ++){
int x;
cin >> x;
dp[i][j] = x + max(dp[i - 1][j],dp[i - 1][j - 1]);//取最值
if(i == n - 1) ans = max(ans,dp[i][j]);
}
}
cout << ans;
return 0;
}
5.A7932.数塔升级版
这题和上一题大同小异，二叉改三叉了，最大改成了最小。但是我这题用另外一种方法来解——即用父节点先初始化子节点。看得懂的可以找机会帅一把。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long dp[305][605],a[305][605];
int main(){
memset(dp,0x3c,sizeof dp);
dp[1][1] = 0;
int n;
cin >> n;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= i * 2 - 1;j ++){
cin >> a[i][j];
dp[i][j] += a[i][j];//这里要用+=不然就覆盖掉了
dp[i + 1][j] = min(dp[i + 1][j],dp[i][j]);//先初始化
dp[i + 1][j + 1] = min(dp[i + 1][j + 1],dp[i][j]);
dp[i + 1][j + 2] = min(dp[i + 1][j + 2],dp[i][j]);
}
}
long long ans = 1e9;
for(int i = 1;i <= n * 2 - 1;i ++){
ans = min(ans,dp[n][i]);
}
cout << ans;
return 0;
}
6.A7933.数塔升级版2
这题看起来很难，有的人感觉像是广搜/深搜（结果看了看数据范围直接老实了）。但是我们要有逆向思维，还是从上往下推，具体思路和前两题差不多。只不过找答案的时候记得要在下面中间的格子找。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int dp[205][205];
int main(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
int x;
cin >> x;
if(i == 1){
dp[i][j] = x;
} else {
dp[i][j] = max(max(dp[i - 1][j - 1],dp[i - 1][j]),dp[i - 1][j + 1]) + x;
}
}
}
cout << max(max(dp[n][m / 2],dp[n][m / 2 + 1]),dp[n][m / 2 + 2]);//找答案
return 0;
}
A7931.传球游戏
本体对于新手来说有难度，因为需要开新的一维用来从传一次球推导到传两次球……最后推导到传m次球。初始化DP[1][0]即可，因为一开始的球是在小蛮手里的。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main(){
int n,m;
cin >> n >> m;
dp[1][0] = 1;//初始化
for(int i = 1;i <= m;i ++){
for(int j = 1;j <= n;j ++){
if(j == 1){
dp[j][i] = dp[n][i - 1] + dp[j + 1][i - 1];//判边界
} else if(j == n){
dp[j][i] = dp[j - 1][i - 1] + dp[1][i - 1];
} else {
dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
}
}
}
cout << dp[1][m];//球在小蛮（1）手里 传了（m）次
return 0;
}
8、9.A7934.最长上升子序列 A7956.导弹拦截
在题单里面有很多与这两题题相似的题，本帖就讲这两个两个，也算是为下篇开了个头。这两道题都是纯纯的模板题，与数塔相似,都使用贪心思想。在求答案方面有所不同，需要每一位都求一下。
代码如下：
导弹拦截：
#include<bits/stdc++.h>
using namespace std;
int a[5005];
vector<int> dp(5005,0);
int main(){
int n;
cin >> n;
int ans = 0;
a[0] = 1;
for(int i = 0;i < n;i ++) cin >> a[i];
for(int i = 0;i < n;i ++){
int amax = 0;
for(int j = 0;j < i;j ++){
if(dp[j] > amax and a[i] <= a[j]){//符合条件及找最大值
amax = dp[j];
}
}
dp[i] = amax + 1;
ans = max(dp[i],ans);//需要全局找最大值
}
cout << ans;
return 0;
}
最长上升子序列：
#include<bits/stdc++.h>
using namespace std;
int a[5005];
vector<int> dp(5005,0);
int main(){
int n;
cin >> n;
int ans = 0;
a[0] = 1;
for(int i = 0;i < n;i ++) cin >> a[i];
for(int i = 0;i < n;i ++){
int amax = 0;
for(int j = 0;j < i;j ++){
if(dp[j] > amax and a[i] > a[j]){
amax = dp[j];
}
}
dp[i] = amax + 1;
ans = max(dp[i],ans);
}
cout << ans;
return 0;
}
如果本帖对你有用，请点一个赞，支持一下。
（AC君都点了，你不点一下？）
未完待续……
有帮助，赞一个