Question

741. 摘樱桃

English Version

题目描述

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

• 0 表示这个格子是空的，所以你可以穿过它。
• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
• -1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

• 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
• 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0)，只能向上或向左走，并且只能穿越有效的格子；
• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
• 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

 

示例 1：

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。

示例 2：

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

 

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• grid[i][j] 为 -1、0 或 1
• grid[0][0] != -1
• grid[n - 1][n - 1] != -1

解法

方法一：动态规划

线性 DP。题目中，玩家从 (0, 0) 到 (N-1, N-1) 后又重新返回到起始点 (0, 0)，我们可以视为玩家两次从 (0, 0) 出发到 (N-1, N-1)。

定义 dp[k][i1][i2] 表示两次路径同时走了 k 步，并且第一次走到 (i1, k-i1)，第二次走到 (i2, k-i2) 的所有路径中，可获得的樱桃数量的最大值。

类似题型：方格取数、传纸条。

class Solution:
  def cherryPickup(self, grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-inf] * n for _ in range(n)] for _ in range((n << 1) - 1)]
    dp[0][0][0] = grid[0][0]
    for k in range(1, (n << 1) - 1):
      for i1 in range(n):
        for i2 in range(n):
          j1, j2 = k - i1, k - i2
          if (
            not 0 <= j1 < n
            or not 0 <= j2 < n
            or grid[i1][j1] == -1
            or grid[i2][j2] == -1
          ):
            continue
          t = grid[i1][j1]
          if i1 != i2:
            t += grid[i2][j2]
          for x1 in range(i1 - 1, i1 + 1):
            for x2 in range(i2 - 1, i2 + 1):
              if x1 >= 0 and x2 >= 0:
                dp[k][i1][i2] = max(
                  dp[k][i1][i2], dp[k - 1][x1][x2] + t
                )
    return max(0, dp[-1][-1][-1])

class Solution {
  public int cherryPickup(int[][] grid) {
    int n = grid.length;
    int[][][] dp = new int[n * 2][n][n];
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k < n * 2 - 1; ++k) {
      for (int i1 = 0; i1 < n; ++i1) {
        for (int i2 = 0; i2 < n; ++i2) {
          int j1 = k - i1, j2 = k - i2;
          dp[k][i1][i2] = Integer.MIN_VALUE;
          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1
            || grid[i2][j2] == -1) {
            continue;
          }
          int t = grid[i1][j1];
          if (i1 != i2) {
            t += grid[i2][j2];
          }
          for (int x1 = i1 - 1; x1 <= i1; ++x1) {
            for (int x2 = i2 - 1; x2 <= i2; ++x2) {
              if (x1 >= 0 && x2 >= 0) {
                dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);
              }
            }
          }
        }
      }
    }
    return Math.max(0, dp[n * 2 - 2][n - 1][n - 1]);
  }
}

class Solution {
public:
  int cherryPickup(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<vector<int>>> dp(n << 1, vector<vector<int>>(n, vector<int>(n, -1e9)));
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k < n * 2 - 1; ++k) {
      for (int i1 = 0; i1 < n; ++i1) {
        for (int i2 = 0; i2 < n; ++i2) {
          int j1 = k - i1, j2 = k - i2;
          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 || grid[i2][j2] == -1) continue;
          int t = grid[i1][j1];
          if (i1 != i2) t += grid[i2][j2];
          for (int x1 = i1 - 1; x1 <= i1; ++x1)
            for (int x2 = i2 - 1; x2 <= i2; ++x2)
              if (x1 >= 0 && x2 >= 0)
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);
        }
      }
    }
    return max(0, dp[n * 2 - 2][n - 1][n - 1]);
  }
};

func cherryPickup(grid [][]int) int {
  n := len(grid)
  dp := make([][][]int, (n<<1)-1)
  for i := range dp {
    dp[i] = make([][]int, n)
    for j := range dp[i] {
      dp[i][j] = make([]int, n)
    }
  }
  dp[0][0][0] = grid[0][0]
  for k := 1; k < (n<<1)-1; k++ {
    for i1 := 0; i1 < n; i1++ {
      for i2 := 0; i2 < n; i2++ {
        dp[k][i1][i2] = int(-1e9)
        j1, j2 := k-i1, k-i2
        if j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 || grid[i2][j2] == -1 {
          continue
        }
        t := grid[i1][j1]
        if i1 != i2 {
          t += grid[i2][j2]
        }
        for x1 := i1 - 1; x1 <= i1; x1++ {
          for x2 := i2 - 1; x2 <= i2; x2++ {
            if x1 >= 0 && x2 >= 0 {
              dp[k][i1][i2] = max(dp[k][i1][i2], dp[k-1][x1][x2]+t)
            }
          }
        }
      }
    }
  }
  return max(0, dp[n*2-2][n-1][n-1])
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function (grid) {
  const n = grid.length;
  let dp = new Array(n * 2 - 1);
  for (let k = 0; k < dp.length; ++k) {
    dp[k] = new Array(n);
    for (let i = 0; i < n; ++i) {
      dp[k][i] = new Array(n).fill(-1e9);
    }
  }
  dp[0][0][0] = grid[0][0];
  for (let k = 1; k < n * 2 - 1; ++k) {
    for (let i1 = 0; i1 < n; ++i1) {
      for (let i2 = 0; i2 < n; ++i2) {
        const j1 = k - i1,
          j2 = k - i2;
        if (
          j1 < 0 ||
          j1 >= n ||
          j2 < 0 ||
          j2 >= n ||
          grid[i1][j1] == -1 ||
          grid[i2][j2] == -1
        ) {
          continue;
        }
        let t = grid[i1][j1];
        if (i1 != i2) {
          t += grid[i2][j2];
        }
        for (let x1 = i1 - 1; x1 <= i1; ++x1) {
          for (let x2 = i2 - 1; x2 <= i2; ++x2) {
            if (x1 >= 0 && x2 >= 0) {
              dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);
            }
          }
        }
      }
    }
  }
  return Math.max(0, dp[n * 2 - 2][n - 1][n - 1]);
};