[LeetCode] Cherry Pick 2 (Java)

문제는 다음과 같다.

LeetCode Cherry Pick 2

DP와 DFS

DP와 DFS를 써야할 것 같다는 느낌은 들었지만, 조금은 막막했던 문제다. 재귀를 통해 조건이 충족한지 확인하고 return을 하며 최댓값을 모으는 식으로 만들었다. 왼쪽 로봇과 오른쪽 로봇이 서로 영향을 받기 때문에 DP를 3차원 리스트로 만들어야 했다. 또한 위에서 어떠한 값을 받았느냐에 따라 리턴 값이 달라지기 때문에 DP에 값을 넣을 때 위에서 받아온 값을 빼서 DP에 저장했다.

import java.util.Arrays;

class Solution {

    int h;
    int w;

    int[] dx = new int[]{- 1, 0, 1};

    int[][][]dp;


    public int dfs(int[][] g, int lp, int rp,int cherry, int cnt) {
        if (cnt == h) {
            return cherry;
        } else{
            cherry += g[cnt][lp] + g[cnt][rp];
            if (dp[cnt][lp][rp] != -1) {
                return dp[cnt][lp][rp] + cherry ;
            }
            cnt++;
            int maxV = 0;
            for (int i = 0; i < 3; i++) {
                int tmpL = lp + dx[i];
                if (tmpL >= 0 && tmpL < w - 1) {
                    for (int j = 0; j < 3; j++) {
                        int tmpR = rp + dx[j];
                        if (tmpR > tmpL && tmpR < w) {
                            maxV = Math.max(maxV, dfs(g, tmpL, tmpR, cherry, cnt));
                        }
                    }
                }
            }
            dp[cnt - 1][lp][rp] = maxV - cherry;
            return maxV;
        }
    }

    public int cherryPickup(int[][] grid) {
        h =  grid.length;
        w = grid[0].length;
        dp = new int[h][w][w];
        for (int[][] arr1 : dp) {
            for (int[] arr2 : arr1) {
                Arrays.fill(arr2, -1);
            }
        }
        int res = dfs(grid, 0, w - 1, 0, 0);
        System.out.println(res);
        return res;
    }
}