clean java dp code


  • 0
    A
    class Solution {
        public int cherryPickup(int[][] grid) {
            int[][][] dp = new int[grid.length * 2][grid.length * 2][grid.length * 2];
            for (int i = 0; i < dp.length; i++){
                for (int j = 0; j < dp[i].length; j++){
                    Arrays.fill(dp[i][j], -1);
                }
            }
            dp[0][0][0] = grid[0][0];
            for (int i = 1; i < 2 * grid.length - 1; i++){
                int[] startP = (i < grid.length) ? new int[]{i, 0} : new int[]{grid.length - 1, i - grid.length + 1};
                for (int j = 0; startP[0] - j >= 0 && startP[1] + j < grid.length; j++){
                    int[] curj = {startP[0] - j, startP[1] + j};
                    if (grid[curj[0]][curj[1]] == -1) continue;
                    for (int k = j; startP[0] - k >= 0 && startP[1] + k < grid.length; k++){
                            int[] curk = {startP[0] - k, startP[1] + k};
                            if (grid[curk[0]][curk[1]] == -1) continue;
                            if (i < grid.length){
                                if (j > 0 && dp[i - 1][j - 1][k] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k]);
                                }
                                if (j > 0 && k > 0 && dp[i - 1][j - 1][k - 1] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k - 1]);
                                }
                                if (k > 0 && dp[i - 1][j][k - 1] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k - 1]);
                                }
                            }else{
                                if (k + 1 < grid.length && dp[i - 1][j][k + 1] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k + 1]);
                                }
                                if (j + 1 < grid.length && k + 1 < grid.length && dp[i - 1][j + 1][k + 1] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j + 1][k + 1]);
                                }
                                if (j + 1 < grid.length && dp[i - 1][j + 1][k] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j + 1][k]);
                                }
                            }
                            if (dp[i - 1][j][k] != -1){
                                    dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k]);
                            }
                            if (dp[i][j][k] != -1){
                                dp[i][j][k] += j != k ? grid[curj[0]][curj[1]] + grid[curk[0]][curk[1]] : grid[curj[0]][curj[1]];
                            }
                        }
                    }
                }
           // System.out.println(dp[6][1][1]);
            return Math.max(dp[2 * grid.length - 2][0][0], 0);
        }
    }
    

  • 0
    A
    class Solution {
        public int cherryPickup(int[][] grid) {
            int[][] dp = new int[grid.length][grid.length];
            for (int i = 0; i < dp.length; i++)
                Arrays.fill(dp[i], -1);
            dp[0][0] = grid[0][0];
            for (int i = 1; i < 2 * grid.length - 1; i++){
                for (int j = Math.min(i + 1, grid.length) - 1; j >= Math.max(0, i - grid.length + 1); j--){
                    int[] curj = {i - j, j};
                    for (int k = j; k >= Math.max(0, i - grid.length + 1); k--){
                        int[] curk = {i - k, k};
                        int tmp = dp[j][k];
                        dp[j][k] = -1;
                        if (grid[curk[0]][curk[1]] == -1) continue;
                        if (grid[curj[0]][curj[1]] == -1) continue;
                        dp[j][k] = tmp;
                        if (j > 0){
                            dp[j][k] = Math.max(dp[j][k], dp[j - 1][k]);
                        }
                        if (k > 0){
                            dp[j][k] = Math.max(dp[j][k], dp[j][k - 1]);
                        }
                        if (j > 0 && k > 0){
                            dp[j][k] = Math.max(dp[j][k], dp[j - 1][k - 1]);
                        }
                        if (dp[j][k] != -1){
                            dp[j][k] += j == k ? grid[curj[0]][curj[1]] : grid[curj[0]][curj[1]] + grid[curk[0]][curk[1]]; 
                        }
                    }
                }
            }
            return Math.max(0, dp[grid.length - 1][grid.length - 1]);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.