#include<bits/stdc++.h> using namespace std; const int N=1e3+11; int main() { int m[N][N],dp[N][N],i,j,n,max1=0; cin>>n; for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ cin>>m[i][j]; } } for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j]; if(dp[i][j]>max1){ max1=dp[i][j]; } } } cout<<max1; return 0; }

典型动态规划模板题

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

int num[10005][10005];

int main(void)
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <=i; j++)
		{
			cin >> num[i][j];
		}
	}//输入数塔
	
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (num[i - 1][j-1] > num[i - 1][j]) num[i][j] += num[i - 1][j-1];
			else num[i][j] += num[i - 1][j];
		}
	}//因为我定义的是全局变量，所以默认初始化为0了，就不用写边界判断

	int max = -1;
	for (int i = 1; i <= n; i++)
	{
		if (num[n][i] > max) max = num[n][i];
	}//最后一排最大的就是所求答案

	cout << max;

	return 0;
}