[프로그래머스] 정수 삼각형 DP 풀이 (자바)

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

프로그래머스

 

 

정수로 이루어진 삼각형에서 

꼭대기에서 출발하여 가장 아래로 내려올 때 최대 값을 구하는 문제

---

풀이

bottom - up 으로 DP를 사용해서 풀었다.  맨 아래서 부터 시작하여 아래에서 올 수 있는 최대값을 더해나가면서 0, 0에 도달했을 때 값을 출력한다. 

 

점화식

dp[n][m] = n번 줄의 m 번째 원소에 도착할 때 최대값

dp[n][m] = Max ( dp[n+1][m], dp[n+1][m+1] ) + triangle[n][m]

 

초기화 : triangle 마지막줄 원소를 dp에 삽입 

class Solution {
    public int solution(int[][] triangle) {
        int[][] dp = new int[triangle.length][triangle.length];
        
        // dp[n][m] = Max ( dp[n+1][m], dp[n+1][m+1]
        int size = triangle.length;
        
        for(int i = 0; i<triangle[size-1].length; i++) {
            dp[size-1][i] = triangle[size-1][i];
        }
        
        for(int i = triangle.length - 2; i>=0; i--) {
            for(int j = 0; j<triangle[i].length; j++) {
                dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
            }
        }
        
        return dp[0][0];
    }
}