Cherry Pickup II Leetcode 문제

체리 필드를 나타내는 행 x 열 매트릭스 그리드가 제공되며 여기서 grid[i][j]는 (i, j) 셀에서 수집할 수 있는 체리 수를 나타냅니다.

체리를 수집할 수 있는 두 대의 로봇이 있습니다.
  • 로봇 #1은 왼쪽 상단 모서리(0, 0)에 있으며
  • 로봇 #2는 오른쪽 상단 모서리에 있습니다(0, 열 - 1).

  • 아래 규칙에 따라 두 로봇을 사용하여 체리 수집의 최대 수를 반환합니다.
  • 셀 (i, j)에서 로봇은 셀 (i + 1, j - 1), (i + 1, j) 또는 (i + 1, j + 1)로 이동할 수 있습니다.
  • 로봇이 셀을 통과하면 모든 체리를 집어 들고 셀은 빈 셀이 됩니다.
  • 두 로봇이 같은 감방에 있으면 한 로봇만 체리를 가져갑니다.
  • 두 로봇 모두 언제라도 그리드 밖으로 이동할 수 없습니다.
  • 두 로봇 모두 그리드의 맨 아래 행에 도달해야 합니다.

  • Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
    Output: 24
    Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
    Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
    Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
    Total of cherries: 12 + 12 = 24.

    class Solution {
        // we will use 3dp for optimizing this problem
        public int cherryPickup(int[][] grid) {
            // since both the robots are moving simultaneously hence they will 
            // be at the same row all the time.
            // hence only one row index is needed .
            // j1 is for robot1 and j2 is for robot2
            int dp[][][] = new int[grid.length][grid[0].length][grid[0].length];
            for(int i =0;i<dp.length;i++){
                for(int matrix[] : dp[i]){
                    Arrays.fill(matrix,-1);
                }
            }
            return solve(grid,0,0,grid[0].length-1,dp);
        }
        public int solve(int[][] grid, int i,int j1,int j2,int [][][] dp){
            if(j1<0 || j2<0 || j1>=grid[0].length || j2 >= grid[0].length) return 0;
            if(i == grid.length-1) {
                // here are two cases , either both robot1 and robot2 have arrived at the same cell in the last row or different cells in the last row
                if(j1==j2) return grid[i][j1];
                else return grid[i][j1] + grid[i][j2];
            }
            if(dp[i][j1][j2]!=-1) return dp[i][j1][j2];
            int maximum = 0;
            /*
            for every move of robot1 robot2 has the chance to move either rightdiagonal or down or left diagonal
            hence the below code will run for 9 times 
            3*3
            */
            for(int a = j1-1;a<=j1+1;a++){
                for(int b = j2-1;b<=j2+1;b++){
                    if(j1==j2) { // since j1 and j2 are same that means robot1 and robot2 are at the same cell . Hence take current cell value + solve() again we can take index j1 or j2 any one as the value at the cell is same
                        maximum =Integer.max(maximum,grid[i][j1]+solve(grid,i+1,a,b,dp));
                    }
                    else {
                        maximum =Integer.max(maximum,  grid[i][j1]+grid[i][j2] + solve(grid,i+1,a,b,dp));
                    }
                }
            }
            return dp[i][j1][j2] = maximum;
        }
    }
    

    좋은 웹페이지 즐겨찾기