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

문제 설명

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

문제 풀이

• 간단한 다이나믹 프로그래밍 문제이다.
• dp[x][y] : x로우, y칼럼에서부터 바닥까지 경로의 합중 최대값

소스 코드 (JAVA)

import java.util.*;

class Solution {
    int[][] map;
    int[][] dp;
    
    public int solve(int x, int y) {
        //기저조건 
        if (x == dp.length - 1)
            return map[x][y];
        if (dp[x][y] != -1) 
            return dp[x][y];
        //다음 노드로 이동 
        int res = map[x][y];
        res += Math.max(solve(x+1, y), solve(x+1, y+1));
        return dp[x][y] = res;
    }
    
    public int solution(int[][] triangle) {
        //초기화 
        map = triangle;
        dp = new int[triangle.length][triangle[triangle.length - 1].length];
        for (int i = 0; i < triangle.length; i++) 
            Arrays.fill(dp[i], -1);
        return solve(0, 0);
    }
}