[DP] 정수 삼각형

 

문제

 

 

접근법

 

* 도형 형식으로 경로가 존재하고, 이동시 거쳐간 최댓값을 구하는 문제 = DP 유형

 

1) 가장 작은 문제의 정의를 점화식으로 구현한다.

 

 

코드

 

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

using namespace std;

int solution(vector<vector<int>> triangle)
{
    vector<vector<int>> C=triangle;

    int y_max= triangle.size();

    for(int y=1;y<y_max;y++)
    {
        for(int x=0;x<=y;x++)
        {
            if(x==0) C[y][x] = C[y-1][x] + triangle[y][x];
            else if(x==y) C[y][x] = C[y-1][x-1] + triangle[y][x];
            else C[y][x] = max(C[y-1][x-1],C[y-1][x]) + triangle[y][x];
        }
    }

    int max = *max_element(C[y_max-1].begin(),C[y_max-1].end());

    return max;
}