[백준] 정수 삼각형_1932

그 위치에서 선택할 수 있는 수의 최대의 합을 cache에 저장하면서 배열의 끝까지 내려가는 dfs이다. 결국 dfs가 모두 끝난 뒤에는 0,0 위치에서 구할 수 있는 최대의 합이 나온다. 

#include <iostream>
#include <string.h>
using namespace std;
 
int n;
int tr[500][500];
int cache[500][500];
int ans = 0;
int max(int a, int b) { return a > b ? a : b; }
 
int dfs(int y, int x) {
    if (y == n) return 0;
    int& ret = cache[y][x];
    if (cache[y][x] != -1) return cache[y][x];
    ret = tr[y][x];
    ret += max(dfs(y + 1, x),dfs(y + 1, x + 1));
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n; 
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            cin >> tr[i][j];
        }
    }
    ans = dfs(0, 0);
    cout << ans;
    return 0;
}