[프로그래머스] 정수 삼각형

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int dp[501][501];
int solution(vector<vector<int>> triangle) 
{
    int answer = 0;
    dp[0][0] = triangle[0][0];

    int iSize = triangle.size();
    
    for(int i=1; i<iSize; i++)
    {
        for(int j=0; j<=i; j++)
        {
            if(j==0) //맨ㄴ왼쪽
            {
                dp[i][j] = triangle[i][j] + dp[i-1][j];
            }
            
            else if(j==i) //맨오른쪽
            {
                dp[i][j] = triangle[i][j] + dp[i-1][j-1];
            }
            else //나머지
            {
                 dp[i][j] =triangle[i][j] +max(dp[i-1][j], + dp[i-1][j-1]);
            }
        }
        
    }
    for(int i=0; i<iSize; i++)
    {
        answer = max(answer,dp[iSize-1][i]);
    }
    return answer;
}

점화식을 세워 DP 바텀업 방식으로 풀었다.

재귀 사용해서 탑다운 방식으로 처음에 접근했지만 너무 어렵다 재귀 DPS관련 문제를 더 봐야할듯!