三角形 （C语言代码）

#include<iostream> 
#include<algorithm>

using namespace std;

int main()
{
	int n, m, i, j, Max;
	int dp[100][100], a[100][100];

	scanf("%d", &n);

	while (n--)
	{
		scanf("%d", &m);

		for (i = 0; i < m; i++)
			for (j = 0; j <= i; j++)
				scanf("%d", &a[i][j]);

		dp[0][0] = a[0][0];
		Max = 0;
		for(i = 1; i < m; i++)
			for (j = 0; j <= i; j++)
			{
				if (j == 0) dp[i][j] = dp[i - 1][j] + a[i][j];
				else if (i == j) dp[i][j] = dp[i - 1][j - 1] + a[i][j];
				else dp[i][j] = max((dp[i - 1][j - 1] + a[i][j]), (dp[i - 1][j] + a[i][j]));

				Max = max(dp[i][j], Max);
			}

		printf("%d\n", Max);
	}

	return 0;
}