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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

코드

class Solution {
    public int solution(int[][] triangle) {
        
        int dp [][] = new int [triangle.length][triangle.length];
        
        dp[0][0] = triangle[0][0];
        dp[1][0] = triangle[1][0] + dp[0][0];
        dp[1][1] = triangle[1][1] + dp[0][0];
        
        for(int i=2;i<triangle.length;i++){
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
            
            for(int j=1;j<i;j++){
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
        
            
        int answer = 0;
        
        for(int i=0;i<triangle.length;i++){
            if(answer < dp[triangle.length-1][i])
                answer = dp[triangle.length-1][i];
        }
        
        return answer;
    }
}