[프로그래머스] 정수 삼각형 (Java)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

1. 주의할 점

- DFS가 아닌 점화식을 통해 문제를 해결한다

 

2. 구현

- DP[][]를 통해 각 지점까지 거쳐간 숫자들의 합의 최대값을 저장한다

- 해당 지점에서 왼쪽 아래와 오른쪽 아래로 갔을 때 각 지점의 최대값을 갱신한다

- 가장 아랫변에 위치한 DP[][]값의 최대값을 반환한다

import java.util.*;
import java.io.*;

class Solution {
    static int dp[][];

    public int solution(int[][] triangle) {
        int answer = 0;
        int num = triangle.length;
        dp = new int[num][num];
        dp[0][0]=triangle[0][0];
        for(int i=0;i<num-1;i++){
            for(int j=0;j<=i;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]);  //왼쪽   
            }
        }
        for(int i=0;i<num;i++)
            answer = Math.max(answer,dp[num-1][i]);
        return answer;
    }
}