【算法教程】【C/C++】DP(动态规划):简单动规问题——程序设计思路与代码实现

faryou2个月前 (08-10)技术教程

前言

        上一篇文章中介绍了递推,其实也是为今天的DP打好基础。


程序设计思路

        DP本质上就是对题目进行分类讨论,列出其不同情况下的状态转移方程,然后套上循环求解。

        DP的种类有很多,其应用范围几乎涵盖了全部的算法内容,理论上来说,只要你有能力列出状态转移方程,DP可以解决几乎一切问题。今天我们讲一下简单的DP,了解一下DP的思路。


代码实现

        由于DP的可拓展性太强,今天我破例用两道题进行讲解:

IMG_20240822_173300.png

        这道题要求我们得到最大的和。这里有一个思路:每次将金字塔底部相邻的两个数相比较,将大者加到这两个数正上方的数上。即:f[x][y]=max(f[x][y+1],f[x+1][y+1])+f[x][y](金字塔存储为直角三角形)。下面是代码:

#include <bits/stdc++.h>

int r,f[1005][1005];//r如题意,f为DP用数组

int main(){
	scanf("%d",&r);
	for(int i=0;i<r;i++) for(int j=0;j<i+1;j++) scanf("%d",&f[i][j]);//读入数据
	for(int i=r-1;i>0;i--) for(int j=0;j<r-1;j++) f[i-1][j]+=max(f[i][j],f[i][j+1]);//递推式
	printf("%d",f[0][0]);//输出塔尖
	return 0;
}

        这道题是经典动规题,我们通过层层上推求出结果。再来看下面这题:

IMG_20240822_174107.png

        本题初看没有思路,但是细细一想,一个长度为n的上升子序列可以分为前面长度为n-1的上升子序列和后面的一个数,那么我们可以先把所有f[x]都初始化为1,之后用双层循环(双指针),将后面的大数和前面的子序列拼为一个序列。由此,我们可以列出这样的方程:f[x]=max(f[i],f[j-1])(f[x]表示从第1到第x个数的最长上升子序列长度),下面是代码:

#include <bits/stdc++.h>

int n,ans=0,a[5005]={0},f[5005]={0};

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i]=1;
	}//以上为读入+初始化(一个数自己也算最长上升子序列)
	for(int i=1;i<=n;i++) for(int j=1;j<=i-1;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);//递推式,当找到一个更大的数时,将其加入前面的子序列
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);//拿到最长长度
	printf("%d",ans);//输出
	return 0;
}


结语

        其实DP本身的思路不难,关键在于你能不能找出所有情况。下篇文章,我将介绍背包DP。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/105.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/105.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。