741. 摘樱桃
走到终点再原路返回，可以转换为：两个人同时走，两人会同步保持在一条对角线上，这条对角线就是。
class Solution {
public:
bool inboard(int n, int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
int dp[n + 10][n + 10][2 * n];
memset(dp, 0x80, sizeof(dp)); //-2139062144, 作用相当于 INT_MIN
dp[0][0][0] = grid[0][0];
for (int sum = 0; sum < 2 * n - 1; sum++) {
for (int x1 = 0; x1 <= sum; x1++) {
int y1 = sum - x1;
if (!inboard(n, x1, y1)) continue;
for (int x2 = 0; x2 <= x1; x2++) { // 第二个不需要走到第一个下面，最多走重合
int y2 = sum - x2;
if (!inboard(n, x2, y2)) continue;
int cur = dp[x1][x2][sum];
for (int k1 = 0; k1 < 2; k1++) {
for (int k2 = 0; k2 < 2; k2++) {
int nx1 = x1 + k1, ny1 = y1 + 1 - k1, nx2 = x2 + k2,
ny2 = y2 + 1 - k2;
if (!inboard(n, nx1, ny1) || !inboard(n, nx2, ny2)) continue;
if (grid[nx1][ny1] != -1 && grid[nx2][ny2] != -1) {
int gain = grid[nx1][ny1] + grid[nx2][ny2];
if (nx1 == nx2 && ny1 == ny2) gain = gain ? 1 : 0;
dp[nx1][nx2][sum + 1] = max(dp[nx1][nx2][sum + 1], cur + gain);
}
}
}
}
}
}
int res = dp[n - 1][n - 1][2 * n - 2];
if (res < -1e9) return 0;
return res;
}
};
