C ++中的Cherry Pickup
假设我们有一个NxN的网格，上面充满了樱桃。每个像元具有以下可能的整数之一-
0-表示单元格为空，因此我们可以通过
1-表示单元格包含一个樱桃，我们可以拾取它并通过
-1-表示该单元格包含刺的障碍物
我们必须使用以下几条规则来收集最大数量的樱桃-
通过在有效路径单元格中向右或向下移动，从位置(0,0)开始并在(N-1,N-1)处结束
到达单元格(N-1,N-1)后，通过在有效路径单元格中向左或向上移动返回到(0,0)；
当我们经过包含樱桃的路径单元格时，我们将其拾取并将其变为空单元格（值将为0）；
如果(0,0)与(N-1,N-1)之间没有有效路径，则无法收集樱桃。
所以，如果输入像-
从位置(0,0)开始，向下，向下，向右，向右到达(2,2)，输出将为5。在此单程中，这里采摘了4棵樱桃，基质变成了。
然后，我们将向左，上，上，左返回(0,0)，再捡起一颗樱桃。采摘的樱桃总数为5。
为了解决这个问题，我们将遵循以下步骤-
定义大小为2x2的数组目录：={{{1，0}，{0，1}}
INF：=10^9
定义大小为51x51x51的数组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