DP - 정수 삼각형

프로그래머스 (DP) - 정수 삼각형

해당 문제는 이전 층의 좌,우 dp의 합 중 큰 값과 더하는 문제였습니다. dp(x, y) = triangle(x,y) + MAX(dp(x-1, y좌), dp(x-1, y우)) 라는 것으로 마지막층까지 총 합을 저장한 dbTriangle 이중배열을 만든후 마지막 층의 dp 합 중 가장 큰 값을 return해주었습니다.

    public int solution(int[][] triangle) {
        int height = triangle.length;
        int[][] dpTriangle = new int[height][];
        dpTriangle[0] = new int[]{triangle[0][0]};

        for (int i = 1; i < triangle.length; i++) {
            dpTriangle[i] = new int[triangle[i].length];
            for(int j = 0; j < triangle[i].length; j++) {
                int preN = i - 1;
                int leftX = Math.max(j - 1, 0);
                int rightX = Math.min(j, dpTriangle[preN].length - 1);
                dpTriangle[i][j] = Math.max(dpTriangle[preN][leftX], dpTriangle[preN][rightX]) + triangle[i][j];
            }
        }

        return Arrays.stream(dpTriangle[height - 1]).max().orElse(0);
    }