leetcode 困难题 1463. Cherry Pickup II 摘樱桃 II

Problem: 1463. Cherry Pickup II 摘樱桃 II

动态规划的呢

dp[i][j][k]表示两个机器人在第i行，左侧机器人在第j列，右侧机器人在第k列，此时的最大值

观察可以发现，j需要满足条件 j <= k

递推公式是：共9种情况的，(j-1, k-1), (j-1, k), (j-1, k+1)，(j, k-1), (j, k), (j, k+1)，(j+1, k-1), (j+1, k), (j+1, k+1)，所以只要不在矩阵外面，就可以拿到最大值

特殊情况是j==k，此时只需要累加一次

Code

class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(n+1, vector<int>(n+1, INT_MIN/10)));
dp[1][1][n] = grid[0][0] + grid[0][n-1];
for(int i = 2; i <= m; i++) {
for(int j = 1; j <= n; j++) {
for(int k = n; k >= j; k–) {
if(k > j) {
if(j-1 >= 0) {
dp[i][j][k] = max(dp[i-1][j-1][k-1], dp[i][j][k]);
dp[i][j][k] = max(dp[i-1][j-1][k], dp[i][j][k]);
if(k + 1 <= n) dp[i][j][k] = max(dp[i-1][j-1][k+1], dp[i][j][k]);
}
if(k-1 >= 0) dp[i][j][k] = max(dp[i-1][j][k-1], dp[i][j][k]);
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j][k]);
if(k + 1 <= n) dp[i][j][k] = max(dp[i-1][j][k+1], dp[i][j][k]);
if(j+1 <= n) {
if(j+1 < k-1) dp[i][j][k] = max(dp[i-1][j+1][k-1], dp[i][j][k]);
if(j+1 < k) dp[i][j][k] = max(dp[i-1][j+1][k], dp[i][j][k]);
if(k+1 <= n) dp[i][j][k] = max(dp[i-1][j+1][k+1], dp[i][j][k]);
}
dp[i][j][k] += grid[i-1][j-1] + grid[i-1][k-1];
} else {
if(j-1 >= 0) {
dp[i][j][k] = max(dp[i-1][j-1][k-1], dp[i][j][k]);
dp[i][j][k] = max(dp[i-1][j-1][k], dp[i][j][k]);
if(k + 1 <= n) dp[i][j][k] = max(dp[i-1][j-1][k+1], dp[i][j][k]);
}
// if(k-1 >= 0) dp[i][j][k] = max(dp[i-1][j][k-1], dp[i][j][k]);
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j][k]);
if(k + 1 <= n) dp[i][j][k] = max(dp[i-1][j][k+1], dp[i][j][k]);
if(j+1 <= n) {
// if(j+1 <= k-1) dp[i][j][k] = max(dp[i-1][j+1][k-1], dp[i][j][k]);
// if(j+1 < k) dp[i][j][k] = max(dp[i-1][j+1][k], dp[i][j][k]);
if(k+1 <= n) dp[i][j][k] = max(dp[i-1][j+1][k+1], dp[i][j][k]);
}
dp[i][j][k] += grid[i-1][j-1];
}
}
}
}
int mx = 0;
for(int j = 1; j <= n; j++) {
for(int k = n; k >= j; k–) {
mx = max(mx, dp[m][j][k]);
}
}
return mx;
}
};