三角形 （C++代码）(DP)

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1001;
int D[maxn][maxn];
int DP[maxn][maxn];
int main()
{
	int n, quan;
	cin >> quan;
	while (quan--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++)
				cin >> D[i][j];
		for (int i = 1; i <= n; i++)
			DP[n][i] = D[n][i];
		for(int i=n-1;i>=1;i--)
			for (int j = 1; j <= i; j++)
			{
				DP[i][j] = max(DP[i + 1][j], DP[i + 1][j + 1]) + D[i][j];
			}
		cout << DP[1][1] << endl;
	}
	return 0;
}