[프로그래머스] Level 3 : 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

다이나믹 프로그래밍 문제이다.(DP)

현재 위치에서 대각선으로 뻗었을 때와, 수직으로 뻗었을 때를 비교했을 때 더 큰 쪽으로 끝까지 더한다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
int cache[501][501];

int Path(int y, int x, const vector<vector<int>>& triangle)
{
    if (y == N - 1) return triangle[y][x];

    int& ret = cache[y][x];
    if (ret != -1) return ret;

    return ret = triangle[y][x] + max(Path(y + 1, x + 1, triangle), Path(y + 1, x, triangle));
}

int solution(const vector<vector<int>> triangle) {
    memset(cache, -1, sizeof(cache));
    N = triangle.size();

    int answer = Path(0, 0, triangle);
    return answer;
}