[BOJ] 1932 정수 삼각형

#include <stdio.h>
#include <algorithm>

using namespace std;

int Triangle[1000][1000], dp[1000][1000], num;

int max_hi(int i, int x){
    if (dp[i][x] != -1) return dp[i][x];
    if (i == num + 1) return 0;
    dp[i][x] = max(max_hi(i + 1, x), max_hi(i + 1, x + 1)) + Triangle[i][x];
    return dp[i][x];
}


int main() {
    scanf("%d", &num);
    for (int i = 1 ; i <= num ; i++){
        for (int x = 1 ; x <= i ; x++){
            scanf("%d", &Triangle[i][x]);
            dp[i][x] = -1;
        }
    }
    printf("%d", max_hi(1,1));
}