(二维dp)741. 摘樱桃

741. 摘樱桃

走到终点再原路返回，可以转换为：两个人同时走，两人会同步保持在一条对角线上，这条对角线就是。

class Solution {
 public:
  bool inboard(int n, int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
  int cherryPickup(vector<vector<int>>& grid) {
    int n = grid.size();
    int dp[n + 10][n + 10][2 * n];
    memset(dp, 0x80, sizeof(dp));  //-2139062144, 作用相当于 INT_MIN
    dp[0][0][0] = grid[0][0];
    for (int sum = 0; sum < 2 * n - 1; sum++) {
      for (int x1 = 0; x1 <= sum; x1++) {
        int y1 = sum - x1;
        if (!inboard(n, x1, y1)) continue;
        for (int x2 = 0; x2 <= x1; x2++) {  // 第二个不需要走到第一个下面，最多走重合
          int y2 = sum - x2;
          if (!inboard(n, x2, y2)) continue;
          int cur = dp[x1][x2][sum];

          for (int k1 = 0; k1 < 2; k1++) {
            for (int k2 = 0; k2 < 2; k2++) {
              int nx1 = x1 + k1, ny1 = y1 + 1 - k1, nx2 = x2 + k2,
                  ny2 = y2 + 1 - k2;
              if (!inboard(n, nx1, ny1) || !inboard(n, nx2, ny2)) continue;
              if (grid[nx1][ny1] != -1 && grid[nx2][ny2] != -1) {
                int gain = grid[nx1][ny1] + grid[nx2][ny2];
                if (nx1 == nx2 && ny1 == ny2) gain = gain ? 1 : 0;
                dp[nx1][nx2][sum + 1] = max(dp[nx1][nx2][sum + 1], cur + gain);
              }
            }
          }
        }
      }
    }
    int res = dp[n - 1][n - 1][2 * n - 2];
    if (res < -1e9) return 0;
    return res;
  }
};