三角形 （C++代码）

解题思路:

dp...

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define N 100

using namespace std;

int dp[N + 2][N + 2];
int T[N + 2][N + 2];

void triangle(int n)
{
	//dp边界
	for (int i = 1; i <= n; i++)
		dp[n][i] = T[n][i];
	//逐层向上dp
	for (int i = n; i >= 1; i--)
		for (int j = 1; j <= i; j++)
			dp[i][j] = max(dp[i + 1][j + 1], dp[i + 1][j]) + T[i][j];
}

int main(int argc, char** argv)
{
	int t = 0;
	cin >> t;
	while (t--)
	{
		int n = 0;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				cin >> T[i][j];
			}
		}

		triangle(n);

		cout << dp[1][1] << endl;
	}
	return 0;
}