[프로그래머스] 정수삼각형(c++)

문제 접근

dp문제이다. 현재 위치에서 최대 값이 어떤 것인지 계산하는 방법으로 문제를 접근했다. 그래서 마지막 가장 맨 꼭대기의 값이 최대값이 되도록 하였다.

코드 구현(c++)

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

int cache[501][501];

int dp(int row, int col, int N, const vector<vector<int>> &triangle){
    if(row == N-1) return triangle[row][col];
    int &res = cache[row][col];
    if(res != -1) return res;

    res = triangle[row][col];
    res += max(dp(row+1, col, N, triangle), dp(row + 1, col + 1, N, triangle));
    return res;


}

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    memset(cache, -1, sizeof(cache));
    dp(0,0, triangle.size(), triangle);
    answer = cache[0][0];
    return answer;
}