基础算法02

dp(动态规划)的基本例题，可以浅浅的帮助理解。

例题一

先来看一道很简单的例题：

具体要求如下：

根据格式可以推出状态方程，这个方程不难，主要关注dp思想，找到状态方程，此题不难发现每一个数字只能往下或者往右走，因此每一个位置的最大值就等于其上面或上左位置的最大值，找到每一个数的最大值，这基本就是动态规划的思想。

核心代码如下：

void dpcount()
{

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+number[i][j];
			if(dp[i][j]>ans)	ans=dp[i][j];
		}
	}
}

ac代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int ans;
int dp[1005][1005]={0};
int number[1005][1005]={0};
void dpcount()
{

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+number[i][j];
			if(dp[i][j]>ans)	ans=dp[i][j];
		
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i =1;i<=n;i++)
	{
		for(int j =1;j<=i;j++)
		{
			cin>>number[i][j];
		}
	}
	dpcount();
	cout<<ans;
	return 0;
}