삼각형 위의 최대 경로 수 세기

문제 : https://algospot.com/judge/problem/read/TRIPATHCNT

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 100+1;

int N;

int triangle[MAX][MAX];

int path[MAX][MAX];

int cache[MAX][MAX];

int count(int y, int x)

{

if (y == N - 1) return 1;

int& ret = cache[y][x];

if (ret != -1)

return ret;

ret = 0;

if (path[y + 1][x + 1] >= path[y + 1][x]) ret += count(y + 1, x + 1);

if (path[y + 1][x + 1] <= path[y + 1][x]) ret += count(y + 1, x);

return ret;

}

void path2(int y, int x)

{

for (int x = 0; x < N; ++x)

path[N - 1][x] = triangle[N - 1][x];

for (int i = N - 2; i >= 0; --i)

for (int j = 0; j < i+1; ++j)

path[i][j] = max(path[i + 1][j], path[i + 1][j + 1]) + triangle[i][j];

}

void Init()

{

for (int i = 0; i < N; ++i)

for (int j = 0; j <= i; ++j)

cache[i][j] = -1;

}

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> N;

Init();

for (int i = 0; i < N; ++i)

for (int j = 0; j <= i; ++j)

cin >> triangle[i][j];

path2(0, 0);

int ans = count(0, 0);

cout << ans << endl;

}

}