baekjun 1923. 정수 삼각형

 동적계획법 기본 문제

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int triangle[500][500];
int cache[501][501];
int N;
int getMaxPath(int y, int x) {
    if (y == N)
        return 0;
    int & ret = cache[y][x];
    if (ret != -1)
        return ret;
    return ret = max(getMaxPath(y + 1, x), getMaxPath(y + 1, x + 1)) + triangle[y][x];
}
 
int main() {
 
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    cout << getMaxPath(0, 0) << endl;
    system("pause");
    return 0;
}