※ 引述 《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;
}
};