三角形 （C++代码）(递归+记忆化搜索)

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1001;
int n;
int quan;
int D[maxn][maxn];
int P[maxn][maxn];
int Maxsum(int i, int j)
{
	if (i == n)
		return D[i][j];
	if (P[i + 1][j] && P[i + 1][j + 1])
		return max(P[i + 1][j], P[i + 1][j + 1]) + D[i][j];
	else
	{
		if (!P[i + 1][j])
			P[i + 1][j] = Maxsum(i + 1, j);
		if (!P[i + 1][j + 1])
			P[i + 1][j + 1] = Maxsum(i + 1, j + 1);
		return max(P[i + 1][j], P[i + 1][j + 1]) + D[i][j];
	}
}
int main()
{
	cin >> quan;
	while (quan--)
	{
		memset(P, 0, sizeof(P));
		cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++)
				scanf("%d", &D[i][j]);
		cout << Maxsum(1, 1) << endl;
	}
	return 0;
}