[JAVA / 자바] Lv.3_정수 삼각형 - 프로그래머스

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

프로그래머스

---

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] dp = new int[len][triangle[len - 1].length];
        dp[0][0] = triangle[0][0];
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j]);
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + triangle[i + 1][j + 1]);
            }
        }
        return Arrays.stream(dp[len - 1]).max().getAsInt();
    }
}

💡 DP

풀이

• 트리 위 층에서 누적시켜 나갈 수 있는 방향: dp[i][j] → dp[i+1][j] , dp[i+1][j+1] 가능
• 이때, 최대값을 구해야 하므로 누적할 때 마다 max로 값 비교해 큰 경우만 갱신해줌
• 가능한 최대값은 9999 * 5000 이므로 long형으로 선언해야 함