algospot - trianglepath

//algospot - trianglepath
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<vector<int>> tri;
vector<vector<int>> cache;
 
void init()
{
    cin >> N;
    tri = vector<vector<int>>(N, vector<int>(N));
    cache = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i = 0; i<N; i++)
        for(int j = 0; j<=i; j++)
            cin >> tri[i][j];
}
 
int dp(int x, int y)
{
    if(x == N-1)
        return tri[x][y];
 
    int& ret = cache[x][y];
    if(ret != -1) return ret;
    ret = dp(x+1, y);
    ret = max(ret, dp(x+1, y+1));
    ret += tri[x][y];
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn < C; ++tn)
    {
        init();
        cout << dp(0, 0) << "\n";
    }
}