[pro] 프로그래머스 level3 43105 정수 삼각형 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

전형적인 dp 문제.

 

[코드]

 

class Solution {
    int[][] dp;
    public int solution(int[][] triangle) {
        int answer = 0;
        // 거쳐간 숫자의 최댓값을 return 
        dp = new int[triangle.length][triangle.length];
        
        for(int i=0; i<triangle.length; i++){
            for(int j=0; j<=i; j++){
                dp[i][j] = triangle[i][j];
            }
        }
        
        for(int i=1; i<triangle.length; i++){
            for(int j=0; j<=i; j++){
                if(j==0){
                    dp[i][j] += dp[i-1][j];
                }
                else if(j==i){
                    dp[i][j] += dp[i-1][j-1];
                }
                else{
                    dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
            }
        }
        
                
        answer = dp[triangle.length-1][0];
        for(int i=1; i<triangle.length; i++){
            answer = Math.max(answer, dp[triangle.length-1][i]);
        }
        
        return answer;
    }
}