[lv.3] 정수 삼각형

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

• 문제
  

• 풀이
  
  위에서 점차 내려가는 것이 아닌, 밑 부분, 즉 예시로 들면 가장 밑 부분의 윗 부분에서, 자신의 아래 부분 중 더 큰 것을 더한다.
  dp식으로 정립하면 이렇게 된다.
  n = 배열의 길이, dp[n-1][i] = triangle[n-1][i]
dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
  이후, 가장 최상단인 dp[0][0]을 리턴한다.

• 후기
  아니 배열 길이가 왜 일정하지 않은건데

• 코드

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n+1][n+1];
        for(int i=0; i<n; i++){
            dp[n-1][i] = triangle[n-1][i];
        }
        for(int i=n-1; i>=0; i--){
            for(int j=0; j<triangle[i].length; j++){
                dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
}