View Code of Problem 65

#include<bits/stdc++.h>
using namespace std;
const int imax = 1005;
int a[imax][imax], n, ans;

void dfs(int x, int y, int sum) {
	if (x == n) {
		if (sum > ans)
			ans = sum;
		return;
	}
	dfs(x + 1, y, sum + a[x + 1][y]);
	dfs(x + 1, y + 1, sum + a[x + 1][y + 1]);
}
int main() {
	int t;
	cin >> t;
	while (t--) {

		cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++)
				cin >> a[i][j];
		ans = 0;
		dfs(1,1,a[1][1]);
		cout << ans << endl;
	}
}