1463. Cherry Pickup II

#dp

Problem

Cherry Pickup II - LeetCodeLeetCode

Intuition

Time and Space Complexity

Space Complexity

Solution

class Solution {
  public int cherryPickup(int[][] grid) {
    int R = grid.length, C = grid[0].length;

    // return recursionHelper(0, 0, C-1, R, C, grid);
    // int[][][] dp = new int[R][C][C];

    // for(int[][] row1: dp) {
    //     for(int[] row2: row1) {
    //         Arrays.fill(row2, -1);
    //     }
    // }
    // return memoizationHelper(0, 0, C-1, R, C, grid,dp);
    return tabulationHelper(grid);
  }

  private int tabulationHelper(int[][] grid) {
    // N -> Size of the row
    // R -> No. of rows C-> No. of cols
    // Time Complexity: O(R*C*C) * 9, for every cell it needs to check 9 possible states
    // Space Complexity: O(R*C*C), DP array

    int R = grid.length, C = grid[0].length;
    int[][][] dp = new int[R][C][C];

    // Initialize the base case for the last row
    for (int col1 = 0; col1 < C; col1++) {
      for (int col2 = 0; col2 < C; col2++) {
        if (col1 == col2) {
          // If col1 and col2 are the same, store the cherry value at col1 only
          dp[R - 1][col1][col2] = grid[R - 1][col1];
        } else {
          // If col1 and col2 are different, store the sum of cherry values at both positions
          dp[R - 1][col1][col2] = grid[R - 1][col1] + grid[R - 1][col2];
        }
      }
    }

    // Iterate from the second last row up to the first row
    for (int row = R - 2; row >= 0; row--) {
      for (int col1 = 0; col1 < C; col1++) {
        for (int col2 = 0; col2 < C; col2++) {
          // Initialize the maximum cherries to a very small value
          int maxCherries = Integer.MIN_VALUE;

          for (int d1 = -1; d1 <= 1; d1++) {
            for (int d2 = -1; d2 <= 1; d2++) {
              int current;

              if (col1 == col2) {
                // If col1 and col2 are the same, consider the cherry value at col1 only
                current = grid[row][col1];
              } else {
                // If col1 and col2 are different, consider the cherry values at both positions
                current = grid[row][col1] + grid[row][col2];
              }

              // Check if the next positions are out of bounds
              if (col1 + d1 < 0 || col1 + d1 >= C || col2 + d2 < 0 || col2 + d2 >= C) {
                // Add a large negative value to discourage selecting out-of-bounds positions
                current += (-10e9);
              } else {
                // Add the maximum cherries from the next row at valid positions
                current += dp[row + 1][col1 + d1][col2 + d2];
              }
              // Update the maximum cherries
              maxCherries = Math.max(maxCherries, current);
            }
          }
          // Store the result in the dynamic programming table
          dp[row][col1][col2] = maxCherries;
        }
      }
    }
    // Return the result for the top row at positions (0, 0) and (0, C-1)
    return dp[0][0][C - 1];
  }

  private int memoizationHelper(int row, int col1, int col2, int R, int C, int[][] grid, int[][][] dp) {
    // N -> Size of the row
    // R -> No. of rows C-> No. of cols
    // Time Complexity: O(R*C*C) * 9, for every cell it needs to check 9 possible states
    // Space Complexity: O(R*C*C) + O(N), needs to store recursion stack and DP array

    // Check if col1 or col2 is out of bounds
    if (col1 < 0 || col1 >= C || col2 < 0 || col2 >= C) {
      return Integer.MIN_VALUE;
    }

    // Check if the result is already computed and stored in the memoization table
    if (dp[row][col1][col2] != -1) {
      return dp[row][col1][col2];
    }

    // Check if we have reached the last row
    if (row == R - 1) {
      // If col1 and col2 are the same, return the cherry value at that position
      if (col1 == col2) {
        return grid[row][col1];
      } else {
        // If col1 and col2 are different, return the sum of cherry values at both positions
        return grid[row][col1] + grid[row][col2];
      }
    }

    // Initialize the maximum cherries to a very small value
    int maxCherries = Integer.MIN_VALUE;

    // Explore all possible directions for col1 and col2 in the next row
    for (int d1 = -1; d1 <= 1; d1++) {
      for (int d2 = -1; d2 <= 1; d2++) {
        int current;

        if (col1 == col2) {
          // If col1 and col2 are the same, consider the cherry value at col1 only
          current = grid[row][col1] + recursionHelper(row + 1, col1 + d1, col2 + d2, R, C, grid);
        } else {
          // If col1 and col2 are different, consider the cherry values at both positions
          current = grid[row][col1] + grid[row][col2] + recursionHelper(row + 1, col1 + d1, col2 + d2, R, C, grid);
        }
        // Update the maximum cherries
        maxCherries = Math.max(maxCherries, current);
      }
    }

    // Store the result in the memoization table for future use
    return dp[row][col1][col2] = maxCherries;
  }

  private int recursionHelper(int row, int col1, int col2, int R, int C, int[][] grid) {
    // N -> Size of the row
    // Time Complexity: O(N*9^N), for every row it needs to check 9 possible states
    // Space Complexity: O(N), needs to store recursion stack

    // Check if col1 or col2 is out of bounds
    if (col1 < 0 || col1 >= C || col2 < 0 || col2 >= C) {
      return Integer.MIN_VALUE;
    }

    // Check if we have reached the last row
    if (row == R - 1) {
      // If col1 and col2 are the same, return the cherry value at that position
      if (col1 == col2) {
        return grid[row][col1];
      } else {
        // If col1 and col2 are different, return the sum of cherry values at both positions
        return grid[row][col1] + grid[row][col2];
      }
    }

    // Initialize the maximum cherries to a very small value
    int maxCherries = Integer.MIN_VALUE;

    // Explore all possible directions for col1 and col2 in the next row
    for (int d1 = -1; d1 <= 1; d1++) {
      for (int d2 = -1; d2 <= 1; d2++) {
        int current;

        if (col1 == col2) {
          // If col1 and col2 are the same, consider the cherry value at col1 only
          current = grid[row][col1] + recursionHelper(row + 1, col1 + d1, col2 + d2, R, C, grid);
        } else {
          // If col1 and col2 are different, consider the cherry values at both positions
          current = grid[row][col1] + grid[row][col2] + recursionHelper(row + 1, col1 + d1, col2 + d2, R, C, grid);
        }
        // Update the maximum cherries
        maxCherries = Math.max(maxCherries, current);
      }
    }

    return maxCherries;
  }
}