solution of TRIANGLEPATH

trianglepath.cpp

//https://algospot.com/judge/problem/read/TRIANGLEPATH
#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;

int triangle[101][101];
int cache[101][101];
int N;

int getMaxValue(int x, int y) {
  if (x == N) {
    return 0;
  }

  if (cache[x][y]) {
    return cache[x][y];
  }

  return cache[x][y] =
    triangle[x][y] + max(getMaxValue(x+1, y), getMaxValue(x+1, y+1));
}

int main(void) {
  int T;
  cin >> T;

  while (T-- > 0) {
    cin >> N;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < i+1; j++) {
        cin >> triangle[i][j];
      }
    }
    memset(cache, 0, sizeof(cache));
    cout << getMaxValue(0, 0) << endl;
  }

  return 0;
}