ALGOSPOT TRIANGLEPATH 알고스팟 삼각형 위의 최대 경로

ALGOSPOT TRIANGLEPATH 알고스팟 삼각형 위의 최대 경로

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cassert>
#include<cstring>
using namespace std;
 
int n;
int triangle[101][101];
int cache[101][101];
int maxPath(int depth,int start) {
 
    
    if (depth == n - 1) return (triangle[depth][start]);
 
    int& ret = cache[depth][start];
    if (ret != -1) return ret;
    return ret= max(maxPath(depth + 1, start), maxPath(depth + 1, start+1))   +triangle[depth][start];
}
 
int main()
{
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n;
        int j= 1;
        memset(cache, -1, sizeof(cache));
        for (int i = 0; i < n; i++) {
            for (int p = 0; p <= i; p++) {
                cin >> triangle[i][p];
 
            }
        }
        cout << maxPath(0, 0) << endl << endl;
    }
 
    return 0;
}
 

문제 출처:https://algospot.com/judge/problem/read/TRIANGLEPATH

전체 경로의 최대합을 반환하는것이 아니라 부분 경로의 최대합을 반환한다는 것에 유의 하고 풀어야 한다.

sum이라는 정보가 (depth,start)에서 맨 아래줄까지 내려가는 문제를 해결하는 데 아무 상관이 없다는 사실을

파악한 덕분에 최적 부분 구조 문제를 파악해서 푸는게 핵심입니다.