[C++] 백준(BAEKJOON) 1932

#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n;
int triangle[501][501];
int cache[501][501];
 
int dp(int y, int x){
    if(y == n-1)
        return triangle[y][x];
        
    int& ret = cache[y][x];
    
    if(ret != -1)
        return ret;
        
    return ret = max(dp(y+1, x), dp(y+1, x+1)) + triangle[y][x];
}
 
int main(void){
    scanf("%d", &n);
    
    for (int i = 0; i<n; i++){
        for (int j = 0; j <= i; j++){
            scanf("%d", &triangle[i][j]);
        }
    }
    
    memset(cache, -1, sizeof(cache));
    
    printf("%d", dp(0, 0));
    
    return 0;
}