题目简化

从左上角出发，到右下角的两条可行路径上的樱桃树最大和是多少？

原题目描述

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

• 0 表示这个格子是空的，所以你可以穿过它。
• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
• -1 表示这个格子里有荆棘，挡着你的路。
  你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；

• 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0）；
• 如果在 (0, 0) 和 (N-1, N-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颗樱桃，这是可以摘到的最大值了

提示

• grid 是一个N 乘N 的二维数组，N 的取值范围是1 <= N <= 50
• 每一个 grid[i][j] 都是集合{-1, 0, 1} 其中的一个数。
• 可以保证起点 grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。

思路

线性三维dp

• 状态表示 ：f(s,x1,x2)走了s步，第一条路线和第二条路线当前点的横坐标分别为x1, x2时取得的最大樱桃数
  • 终点一共走 2*n - 1步（因为只能向下、向右两种走法）
  • 相对应的纵坐标为 s - x1, s - x2
• 状态计算 ： 怎么抵达当前位置的 4种转移
  • 两个路线同时右 f(s,x1,x2) = f(s-1,x1, x2) + grid(x1,y1) + grid(x2,y2)
  • 两个路线同时下 f(s,x1,x2) = f(s-1,x1-1, x2-1) + grid(x1,y1) + grid(x2,y2)
  • 一个右，一个下 f(s,x1,x2) = f(s-1,x1, x2 - 1) + grid(x1,y1) + grid(x2,y2)
  • 一个下，一个右 f(s,x1,x2) = f(s-1,x1-1, x2) + grid(x1,y1) + grid(x2,y2)
• 注意
  • 进入相同的格子，结果只能取其一，数要减一
  • 三维向量的声明

c++ 代码

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<vector<int>>> f(2*n - 1, vector<vector<int>> (n, vector<int>(n, INT_MIN)));
        f[0][0][0] = grid[0][0];

        for(int s = 1; s < 2 * n - 1; s ++)
            for(int x1 = 0; x1 < n; x1 ++)
                for(int x2 = 0; x2 < n; x2 ++)
                {
                    int y1 = s - x1;
                    int y2 = s - x2;
                    // 位置出界
                    if(y1 < 0 || y1 >= n || y2 < 0 || y2 >= n)
                        continue;
                    // 特殊格子进不去
                    if(grid[x1][y1] == -1 || grid[x2][y2] == -1)
                        continue;
                    // 如果走到同一个格子 只能取一个
                    int t = grid[x1][y1] + grid[x2][y2];
                    if(x1 == x2 && t > 0)
                        t--;
                    // 右右
                    f[s][x1][x2] = f[s - 1][x1][x2] + t;
                    // 下右
                    if(x1 > 0)
                        f[s][x1][x2] = max(f[s][x1][x2], f[s - 1][x1 - 1][x2] + t);
                    // 右下
                    if(x2 > 0)  
                        f[s][x1][x2] = max(f[s][x1][x2], f[s - 1][x1][x2 - 1] + t);
                    // 下下   
                    if(x1 > 0 && x2 > 0)
                        f[s][x1][x2] = max(f[s][x1][x2], f[s - 1][x1 - 1][x2 - 1] + t);
                }

        return max(0, f[2*n - 2][n - 1][n - 1]);
    }
};

相似题目 LeetCode 1463. 摘樱桃 II

与上述题目不同的是：

• 两个机器人的起点不一样，一个在左上角，一个在右上角 ，且要同时抵达最后一行

• 机器人前进的方向不同 ： 向下 左斜下 右斜下

  • 三种方向选择，所以9种状态转移
  • f(k,i,j)表示 位置分别再grid(k,i) 和grid(k,j) 时的最大收益

• 每个格子的樱桃数目 >= 0, 且无障碍物

• 矩阵是矩形，而不是正方形

  class Solution {
  public:
      int cherryPickup(vector<vector<int>>& grid) {
          int n = grid.size(), m = grid[0].size();
          vector<vector<vector<int>>> f(n, vector<vector<int>>(m, vector<int>(m, -1)));
          // f(k,i,j) 位置分别再grid(k,i) 和grid(k,j) 时的最大收益
          f[0][0][m - 1] = grid[0][0] + grid[0][m - 1]; 

          int res = 0;
          for (int k = 1; k < n; k ++ )
              for (int i = 0; i < m; i ++ )
                  for (int j = 0; j < m; j ++ )
                      // 9钟状态转移
                      for (int a = i - 1; a <= i + 1; a ++ )
                          for (int b = j - 1; b <= j + 1; b ++ )
                          {   // 出界
                              if (a < 0 || a >= m || b < 0 || b >= m) continue;
                              // 无收益直接跳过
                              int t = f[k - 1][a][b];
                              if (t == -1) continue;
                              // 进入同一个格子 只能选一次
                              if (i == j)  // 进入同一个格子只能选一次
                                  t += grid[k][i];
                              else 
                                  t += grid[k][i] + grid[k][j];
                              f[k][i][j] = max(f[k][i][j], t);

                              res = max(res, f[k][i][j]);
                          }
          return res;

      }
  };