정수 삼각형

#include<iostream>

#include<cstdio>

using namespace std;


int n;
int a[501][501];
int d[501][501];

int max(int a, int b){
    int max = a;
    if(max < b)
        max = b;
    return max;
}

int main(){
    scanf("%d", &n);
    int t = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= t; j++ )
        {
            scanf("%d", &a[i][j]);
        }
        t++;
    }
    d[1][1] = a[1][1];
    t = 2;
    for(int i = 2; i <= n; i++){

        for(int j = 1; j <= t; j++){
            if(j == 1)
                d[i][j] = a[i][j] + d[i-1][j];
            else if(j == t){
                d[i][j] = a[i][j] + d[i-1][j - 1];
            }
            else d[i][j] = a[i][j] + max(d[i-1][j], d[i-1][j-1]);

        }
        t++;
    }
    int max = d[n][1];
    for(int i = 2; i <= n; i++){
        if(max < d[n][i])
            max = d[n][i];
    }
    printf("%d\n", max);

    return 0;



}

DP든 BFS든 뭔가 MAX값 찾을때 계속 저런식으로 찾는데 좋지 못한 방법이긴한듯..

점화식 풀어가면서 찾는것도 고려해봐야함

역시 쉬운DP문제