[프로그래머스] 정수 삼각형 [cpp]

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43105
알고리즘 : DP(동적 프로그래밍)

핵심

큰 숫자들만 골라서 합해야함.
큰 숫자를 기준으로 현재 인덱스 또는 +1의 인덱스 중에서 제일 큰 수를 골라야 함.
이런 경우 마지막 행부터 시작하여 위로 올라가며 계산.
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])

계산

1번
       [7]
      [3, 8]
    [8, 1, 0]
  [2, 7, 4, 4]
[4, 5, 2, 6, 5]

2번
       [7]
      [3, 8]
    [8, 1, 0]
  [7,12,10,10]
 [4, 5, 2, 6, 5]
 
 3번
        [7]
      [23,21]
    [20,13,10]
  [7,12,10,10]
 [4, 5, 2, 6, 5]
 
 4번
        [30]
      [23,21]
    [20,13,10]
  [7,12,10,10]
 [4, 5, 2, 6, 5]

---

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    // DP 배열은 triangle과 같은 크기로 초기화
    vector<vector<int>> dp = triangle;

    // n -2인 이유 마지막 행제외하고 그 위부터 위로 계산
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j < dp[i].size(); ++j) {
            // max(dp[i + 1][j], dp[i + 1][j + 1])인 이유는 dp 합산한 결과중에서 가장 큰 값을 현재 i기준의 행의 기본값과 더해서
            // dp i행에 해당하는 j에 값을 더하여 큰수를 판별 할 수 있도록 함.
            // 고로 dp[0][0]이 되는 순간이 제일 큰값이 됨.
            dp[i][j] = triangle[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }

    // 꼭대기의 최댓값 반환
    return dp[0][0];
}