[Lv.3] 정수 삼각형 : Java / DP

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0; // 거쳐간 숫자의 합의 최댓값
        
        int n=triangle.length;
        int[][] dp = new int[n][n];
        
        dp[0][0] = triangle[0][0];
        for(int i=1; i<n; i++){
            for(int j=0; j<=i; j++){
                if(j==0){
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }
                else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                }
                
            }
        }
        
        // 마지막 줄 중 최댓값이 정답
        for(int v: dp[n-1]){
            answer = Math.max(answer, v);
        }
        return answer;
    }
}