프로그래머스 정수 삼각형 Lv3 / JAVA

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

프로그래머스

Top-down 방식으로 풀었다.

> 풀이

import java.util.*;

class Solution {
    static int[][] mem = new int[501][501];
    
    public int solution(int[][] triangle) {
        for(int[] x : mem) {
            Arrays.fill(x, -1);
        }
        return dp(0,0,triangle);
    }

    public int dp(int x, int y, int[][] triangle) {
        if(y == triangle.length) return 0; // 삼각형 바닥까지 가면 종료
        if(mem[x][y] != -1) return mem[x][y]; // 값이 있다면 바로 리턴
        return mem[x][y] = triangle[y][x] + 
            Math.max(dp(x,y+1,triangle), dp(x+1,y+1,triangle));
    }
}