※ 引述 《JIWP (神楽めあ的钱包)》 之铭言：
:
: 1463 Cherry Pickup II
:
: 给一个2维矩阵grid，grid[i][j]代表这个格子的樱桃数量
:
: 有两个机器人会收集格子上的樱桃
:
: 当两个机器人走到同一格的时候，只有一个机器人可以拿grid[i][j]个樱桃，另一个拿0
个
:
: 机器人一个是从左上角grid[0][0]，另一个是从右上角grid[0][cols-1]
:
: 每次可以往左下、正下、右下走
:
: 请问机器人最多可以收集几个樱桃
这题一开始蛮难想的
偷偷看了一下提示之后
哇干 对欸 可以三维
姆咪
思路：
有图应该就很好懂ㄌ
https://i.imgur.com/nstwFsh.jpg
就跟下坠一样 要把每一层的动作分开来讨论
然后
要先知道某一层地方每一种走法的sum
所以会用paper来记录他们
接下来就可以dp了
每一层都用sum来记录走过的总和
然后两个机器人都可以左右一格
所以sum在更新的时候要看自己的九宫格最大的
然后最后再看最后一层最大的就可以了
我beat 99.??% 妈的好爽
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid)
{
int layer = grid.size();
int n = grid[0].size();
int paper[layer][n][n];
int sum[layer][n][n];
for(int l = 0 ; l < layer ; l ++)
{
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
if(i != j)
{
paper[l][i][j] = grid[l][i] + grid[l][j];
}
else if(i == j)
{
paper[l][i][j] = grid[l][i];
}
sum[l][i][j] = -1;
}
}
}
sum[0][n-1][0] = paper[0][n-1][0];
for(int l = 1 ; l < layer ; l ++)
{
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
int lastmax = -1;
if((i-1>=0)&&(j-1>=0))
{
lastmax = max(lastmax , sum[l-1][i-1][j-1]);
}
if((i-1>=0))
{
lastmax = max(lastmax , sum[l-1][i-1][j]);
}
if((i-1>=0)&&(j+1<n))
{
lastmax = max(lastmax , sum[l-1][i-1][j+1]);
}
if((j-1>=0))
{
lastmax = max(lastmax , sum[l-1][i][j-1]);
}
lastmax = max(lastmax , sum[l-1][i][j]);
if(j+1<n)
{
lastmax = max(lastmax , sum[l-1][i][j+1]);
}
if((i+1<n)&&(j-1>=0))
{
lastmax = max(lastmax , sum[l-1][i+1][j-1]);
}
if((i+1<n))
{
lastmax = max(lastmax , sum[l-1][i+1][j]);
}
if((i+1<n)&&(j+1<n))
{
lastmax = max(lastmax , sum[l-1][i+1][j+1]);
}
if(lastmax!=-1)
{
sum[l][i][j] = lastmax + paper[l][i][j];
}
}
}
}
int ans = 0;
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
ans = max(sum[layer-1][i][j] , ans);
}
}
return ans;
}
};