引言

终于熬到动态规划了！！！（呐喊）

学了这么久c++，终于学到这一章了

另外，9月份王文王还要考电子学会6级

求求各位在评论区留个祝福吧！

求求啦！！！（超大声）

简介

老规矩，介绍介绍动态规划：

俗话说，学c++有三座大山要翻，其一是嵌套循环，其二是函数，其三就是动规了，有时候遇上一些题目（例如斐波那契数列、Pell数列等有规律的数列求其中一项这类题）时，会经常出现超时、内存超限的情况，但是因为数列的规律性，又不好直接舍弃一部分算法，这时候就要用到动态规划了。

动态规划的本质就是把一个大问题化为两个或几个小问题，再大事化小小事化无，利用这类题目的前几项简单好算重复性高的特点定好最小子问题的解，然后一步步反推回去最终解决大问题，这中间就有很多可以节省空间开支和时间复杂度开支的地方了。

以斐波那契数列为例，当求数列第n项时，可以用已知条件把它拆解为“F(n-1)+F(n-2)”，再以此类推拆解F(n-1)和F(n-2)，一步步拆就能拆到第一项、第二项和第三项，也就是0and1and1，这样是不是简单多了，熟练一点甚至可以直接用三个变量解决问题。怎么样是不是很方便。

介绍就到这里，接下来就是题目&代码了

正文

接下来要写的代码是c++动态规划的一些典型题目：

核电站问题

#include<bits/stdc++.h>
using namespace std;
int dp[60][6]={0};
int main()
{
	int n,m;
	cin>>n>>m;
	dp[0][0]=1;
	dp[1][0]=1;
	dp[0][1]=1;
	dp[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<m;j++)
		{
			dp[i][0]+=dp[i-1][j];
		}
		for(int j=1;j<m;j++)
		{
			dp[i][j]=dp[i-1][j-1];
		}
		
		/*
		cout<<"输出："<<endl;
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=m;k++)
			{
				cout<<dp[j][k]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;
		 */
	}
	int sum=0;
	for(int i=0;i<=m;i++)
	{
		sum+=dp[n][i];
	}
	cout<<sum;
	
	
	return 0;
}

开餐馆

本体原型为“大盗”，在此基础增加数据组数等以增加难度，也就是：大盗问题pro

#include<bits/stdc++.h>
using namespace std;
struct point
{
	int val;
	int p;
};
int t,n,m;
int sss[1010]={0};
int sl=0;
int main()
{
	cin>>t;
	while(t--)
	{
		point a[1010]={0};
		int dp[1010]={0};
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].p;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].val;
		}
		dp[1]=a[1].val;
		for(int i=2;i<=n;i++)
		{
			//不开店
			dp[i]=dp[i-1];
			//开店 找到距离合适的第一家店
			for(int j=i-1;j>=1;j--)
			{
				if(a[i].p-a[j].p>m)
				{
					dp[i]=dp[j]+a[i].val;
					break;
				}
			}
		}
		sss[sl]=dp[n];
		sl++;
	}
	for(int i=0;i<sl;i++)
	{
		cout<<sss[i]<<endl;
	}
	
	
	
	return 0;
}

吃奶酪

这个问题就属于标准的大盗问题了

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	cin>>m;
	while(m--)
	{
		cin>>n;
		int a[1010]={0};
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		int dp[100010]={0};
		dp[0]=a[0];
		dp[1]=max(a[0],a[1]);
		for(int i=2;i<n;i++)
		{
			dp[i]=max(dp[i-2]+a[i],dp[i-1]);
		}
		cout<<dp[n-1]<<endl;
	}
	
	
	return 0;
}

求关注点赞收藏评论！！！

各位，王文王在这里跪求点赞收藏！！！

有段时间没更新，这次更完希望可以看到老粉的点赞和新粉的关注（可怜巴巴）

求求啦！！！