典型动态规划模板题

#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;
}