[프로그래머스][정수삼각형]-Lv.3

🎊 문제

문제링크

🎊 제한 사항

🎊 접근방법

위 모양처럼 생각하면 쉽게 접근할 수 있다.
1. 자신의 위에 있는 숫자와 왼쪽대각선의 숫자를 비교한 뒤 더 큰 숫자와 자신을 더하고 저장한다.
2. 마지막 행까지 1번을 반복한다.
3. 마지막 행을 반복할 때 Math.max를 이용하여 최댓값을 구한다.

🎊 코드

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