[종만북] [8장 동적 계획법] 8.4장 삼각형 위의 최대 경로

Approach

path(y, x) : (y, x)ㄱ에서 시작해서 맨 아래줄까지 재려가는 부분 경로의 최대합

이렇게 정의했을 경우, path(y, x)는 y ~ n - 1까지의 아직 해결하지 못한 조각들에 대한 값을 정의하는 부분이므로 이전 입력값에 영향을 받지 않는다. 

 

즉, (y, x)까지 어떤 경로로 도착했건 남은 부분 문제는 항상 최적으로 풀어도 상관이 없다. 이러한 성질을 최적 부분 구조(Optimal substructure)이라고 한다. 이러한 성질 때문에 지금까지의 선택과 관계 없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 알 수 있게 되는 것이다. 따라서 탑-다운 방식으로 이 문제를 해결할 수 있게 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int triangle[101][101];
int dp[101][101];
int n;

int memoization(int x, int y){
    if(x == n) return triangle[x][y];
    int& ret = dp[x][y];
    if(ret != -1) return ret;
    else{
        return ret = max(memoization(x + 1, y), memoization(x + 1, y + 1)) + triangle[x][y];
    }
}

int main(void){
    fastio;
    int t;
    cin >> t;
    while(t--){
        memset(dp, -1, sizeof(dp));
        cin >> n;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                cin >> triangle[i][j];
            }
        }
        cout << memoization(1, 1) << "\n";
    }
}