[DP]문제#7.정수삼각형(프로그래머스)

코딩테스트 연습 - 정수 삼각형 | 프로그래머스 (programmers.co.kr)

​

d이라는 이차원 배열에 데이터를 저장하여 해를 구해였다.

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