[JAVA] DP : 정수 삼각형

1.문제 내용

요약
삼각형 꼭대기부터 자식노드 2개 중 하나를 더하여 바닥까지 더했을 때 최대값 구하기

2. 접근방법
간단하게 재귀 함수를 통해 구현해 보았는데 시간초과가 발생해서 원인을 고민해보니 같은 문제를 탐색하는 과정이 있어서 그런거였다. 그래서 이를 해결하기위해 DP를 알아보게 되었고 DP를 사용해 풀어보기로 하였다

3. 구현과정

class Solution {
    public int solution(int[][] triangle) {
        int answer = getMax(triangle, 0, 0);
        return answer;
    }
    public int getMax(int[][] triangle, int x, int y) {
        if(x == triangle.length - 1) return triangle[x][y];
        int left = triangle[x][y] + getMax(triangle, x+1, y);
        int right = triangle[x][y] + getMax(triangle, x+1, y+1);
        return Math.max(left, right);
    }
}

우선 재귀함수만 사용한 풀이이다. 이 풀이로 진행하게되면 시간초과로 문제가 틀리게 되는데 DP로 수정해보자

int[][] dp = new int[500][500];

문제에서는 삼각형의 최대 높이가 500이라 하였으니 연산기록을 메모이제이션할 2차원배열 선언

public int getMax(int[][] triangle, int x, int y) {
    if(x == triangle.length - 1) return triangle[x][y];
    if(dp[x][y] != 0) return dp[x][y];
    int result = Math.max(
        triangle[x][y] + getMax(triangle, x+1, y),
        triangle[x][y] + getMax(triangle, x+1, y+1)
    );
    dp[x][y] = result;
    return result;
}

DP를 활용해 변경한 getMax
dp배열에 값이 저장했는지 기록을 확인하면서 프로그램이 수행된다
수정하는김에 left right를 따로 선언하지 않고 값을 저장했다

4. 결과

전체코드

class Solution {
    int[][] dp = new int[500][500];
    public int solution(int[][] triangle) {
        int answer = getMax(triangle, 0, 0);
        return answer;
    }
    public int getMax(int[][] triangle, int x, int y) {
        if(x == triangle.length - 1) return triangle[x][y];
        if(dp[x][y] != 0) return dp[x][y];
        int result = Math.max(
                triangle[x][y] + getMax(triangle, x+1, y),
                triangle[x][y] + getMax(triangle, x+1, y+1)
        );
        dp[x][y] = result;
        return result;
    }
}