프로그래머스 - 정수 삼각형(동적계획법)

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

처음에 코드
모든 경우의 수를 다 확인해보고 그 중 최댓값을 찾는 구조..
몇 개는 맞는데 정확성 안맞는 것도 있고 효율성은 아예 안맞더라..

class Solution {
    int answer = 0;
    int h;
    int[][] tri = new int[h][h];
    void max_triangle(int height, int width, int sum){
        if(height == tri.length-1){
            answer = Math.max(answer, sum);
            return;
        }   
        int left = sum + tri[height+1][width];
        int right = sum + tri[height+1][width+1];
        max_triangle(height+1, width, left);
        max_triangle(height+1, width+1, right);
    }
    
    public int solution(int[][] triangle) {
        h = triangle.length;
        tri = triangle;
        
        max_triangle(0, 0, triangle[0][0]);
        return answer;
    }
}

두번째 코드(정답)
중복되는 값 중 작은 값은 저장할 필요가 없다는게 포인트!

1. triangle와 같은 구조의 이차원 배열 dp를 만들어주고
   dp[0][0]에 trinagle[0][0]을 대입한다.

2. height에 따른 반복문을 돌면서 dp를 채워준다.
   이때, dp의 양쪽 끝은 (이전 dp)+(현재 triangle값)이므로 따로 더해주고
   나머지 dp 값은 이전 height의 dp값 왼쪽과 오른쪽 중 최대값을 골라 현재 triangle값과 더해준다.

3. 제일 큰 height에서 최대값을 골라 answer에 대입한다.

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