View Code of Problem 65

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005], ans,n ;
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--) {
		ans=0;
		
		cin >> n;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++)
				cin >> a[i][j];
		}
		dfs(1,1,a[1][1]);
		cout<<ans<<endl;

	}
}