C++:: 프로그래머스 < 정수 삼각형 >

간단한 dp문제이다. 주의할 점은 주어지는 triangle의 배열 크기가 n x m 크기로 들어오는게 아니라는 점이다.

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

int solution(vector<vector<int>> triangle) {
    int answer = 0, n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    dp[0][0] = triangle[0][0];
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            triangle[i].push_back(0);
        }
    }
    for (int i=1; i<n; i++) {
        dp[i][0] = dp[i-1][0] + triangle[i][0];
        for (int j=1; j<i+1; j++) {
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            answer = max(dp[i][j], answer);
        }
    }
    return answer;
}