假设我们有一个N x N的网格，上面充满了樱桃。每个像元具有以下可能的整数之一-
0-表示单元格为空，因此我们可以通过
1-表示单元格包含一个樱桃，我们可以拾取它并通过
-1-表示该单元格包含刺的障碍物
我们必须使用以下几条规则来收集最大数量的樱桃-
通过在有效路径单元格中向右或向下移动，从位置(0,0)开始并在(N-1,N-1)处结束
到达单元格(N-1,N-1)后，通过在有效路径单元格中向左或向上移动返回到(0,0)；
当我们经过包含樱桃的路径单元格时，我们将其拾取并将其变为空单元格（值将为0）；
如果(0,0)与(N-1,N-1)之间没有有效路径，则无法收集樱桃。
所以，如果输入像-
| 0 | 1 | -1 |
| 1 | 0 | -1 |
| 1 | 1 | 1 |
从位置(0,0)开始，向下，向下，向右，向右到达(2,2)，输出将为5。在此单程中，这里采摘了4棵樱桃，基质变成了。
| 0 | 1 | -1 |
| 0 | 0 | -1 |
| 0 | 0 | 0 |
然后，我们将向左，上，上，左返回(0,0)，再捡起一颗樱桃。采摘的樱桃总数为5。
为了解决这个问题，我们将遵循以下步骤-
定义大小为2 x 2的数组目录：= {{{1，0}，{0，1}}
INF：= 10 ^ 9
定义大小为51 x 51 x 51的数组dp。
定义一个函数solve()，它将使用r1，c1，c2，一个2D数组>＆grid，
n：=网格大小，r2：= r1 + c1-c2，ret：= 0
m：=（如果n为非零，则为grid [0]的大小，否则为0）
如果r1 <0或c1 <0或r2 <0或c2 <0或r1> = n或r2> = n或c1> = m或c2> = m，则-
返回-INF
如果grid [r1，c1]与-1相同，或者grid [r2，c2]与-1相同，则-
返回-INF
如果r1与r2相同，并且c1与c2相同，并且r1与n-1相同，而c1与m-1相同，则-
返回网格[r1，c1]
如果dp [r1，c1，c2]不等于-1，则-
返回dp [r1，c1，c2]
ret：= ret + grid [r1，c1]
如果r1与r2相同且c1与c2相同，则：不执行任何操作
除此以外
ret：= ret + grid [r2，c2]
温度：= -INF
对于初始化k：= 0，当k <2时，更新（将k增加1），执行-
temp：= temp和solve（r1 + dir [k，0]，c1 + dir [k，1]，c2 + 1，网格的最大值）
temp：= temp和solve（r1 + dir [k，0]，c1 + dir [k，1]，c2，grid）的最大值
返回dp [r1，c1，c2] = ret + temp
从主要方法中，执行以下操作-
用-1填充dp
ret：= solve（0，0，0，网格）
返回最大值0并退出
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
int dp[51][51][51];
int solve(int r1, int c1, int c2, vector < vector <int> >& grid){
int n = grid.size();
int r2 = r1 + c1 - c2;
int ret = 0;
int m = n? grid[0].size() : 0;
if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
ret += grid[r1][c1];
if(r1 == r2 && c1 == c2){
}else ret += grid[r2][c2];
int temp = -INF;
for(int k = 0; k < 2; k++){
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
}
return dp[r1][c1][c2] = ret + temp;
}
int cherryPickup(vector<vector<int>>& grid) {
memset(dp, -1, sizeof(dp));
int ret = solve(0, 0, 0, grid);
return max(0, ret);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
cout << (ob.cherryPickup(v));
}{{0,1,-1},{1,0,-1},{1,1,1}}输出结果
5