DP_백준_정수 삼각형_1932

1. 정의 : dp[n][m] : n행 m열 일때 합이 최대가 되는 경로의 합

2. 점화식 : dp[n][m] = max(dp[n-1][m], dp[n-1][m-1])+value[n][m]

3. 초기화 : dp[0][0] = value[0][0];

4. 반례 : m=0 일때 주의

#include <iostream>
using namespace std;
 
int main() {
    int count;
    cin >> count;
    int ** value = new int*[count];  // input
    int ** dp = new int*[count]; // memoization
 
    for (int i = 0; i < count; i++) {
        value[i] = new int[count];
        dp[i] = new int[count];
    }
 
    for (int i = 0; i < count; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> value[i][j];
        }
        for (int j = 0; j < count; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = value[0][0];
    //Initiallize
    
    for (int i = 1; i <= count - 1; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0||(dp[i-1][j]>dp[i-1][j-1])) {
                dp[i][j] = dp[i - 1][j] + value[i][j];
            }
            else {
                dp[i][j] = dp[i - 1][j - 1] + value[i][j];
            }
        }
    }
 
    int max = 0;
    for (int i = 0; i < count; i++) {
        if (max < dp[count - 1][i]) {
            max = dp[count - 1][i];
        }
    }
    cout << max << endl;
}