[알고리즘] DP-숫자 삼각형

 
#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
 
using namespace std;
 
int dp [1001][1001];
int tr [1001][1001];
 
/*
    a == 0과 마지막줄은 max없음
    dp[n] = board[n][a] + max(dp[n-1][a], dp[n-1][a-1])
*/
 
int _max(int a, int b)
{
    return a > b ? a : b;
}
 
int main()
{
    int n;
    cin >> n;
 
    for(int i =1 ; i < n+1 ; i++){
        for(int a =1 ; a < i+1 ; a++){
            cin >> tr[i][a];
        }
    }
 
    dp[1][1] = tr[1][1];
 
    for(int i =2 ;i <= n ; i++){
            for(int a = 1 ; a <= i ; a++){
 
                    if(a == i)
                    {
                            dp[i][a] = tr[i][a] + dp[i-1][a];
                    }
 
                    if(a == 1) dp[i][a] = tr[i][a] + dp[i-1][a];
                    /*else if(a == i) {
                        dp[i][a] = tr[i][a] + dp[i-1][a];
                    }*/
                  else dp[i][a] = tr[i][a]+_max(dp[i-1][a-1], dp[i-1][a]);
            }
    }
 
 
    int ans = 0;
    for(int  i = 1 ;  i < n+1; i++)
    {
        //cout <<  dp[n][i] << endl;
        if(ans < dp[n][i]) ans = dp[n][i];
    }
    cout << ans ;
 
 
 
 
 
}