[Dynamic Programming] 프로그래머스 정수삼각형

정수 삼각형

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

프로그래머스

dp[i][0]은 좌표 이동 루트가 다르므로 예외처리 해주고 나머지는 같은 로직으로 반복

단, 거쳐간 숫자의 최대 합을 구해야하므로 (현재 위치한 숫자 + 대각선 위 왼쪽과 오른쪽 각각의 값) 비교해주고 더 큰 값만 dp에 저장해주면 된다. 

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

        for(int i = 1; i < dp.length; i++){
            answer = Math.max(answer, dp[len-1][i]);
        }
        
        return answer;
    }
}