力扣741 2024.5.6

原题网址：https://leetcode.cn/problems/cherry-pickup/description/?envType=daily-question&envId=2024-05-06

个人难度评价：1800

分析：
自然的想到分两次dp，第一次dp后修改格点值，然后进行第二次dp。这种做法是错误的：第一次dp的过程中，每次选择都对第二次dp产生后效性。
明显从左上到右下和从右下到左下是等效的，那么能否一次dp中就完成两次？
有dp[i][j][x][y]，i j为第一次的横纵坐标，x y为第二次的横纵坐标，保证两次的步数相同（记为k步），有i+j=x+y=k+2。那么我们就可以得知当前状态下两次是否到达同一格，可以及时制止第二次的转移。
此时实际已经可以通过，但显然有一个可以使代码更简单的优化：既然i+j=x+y=k+2恒成立，那么j与y显然可以省略，只需要k i x三维即可。
那么最终做法显然dp[k][i][x],枚举k与每个合法i x，转移显然四种：
从右右来， 从右下来， 从下右来， 从下右来。
注意处理荆棘导致的不可达

源码：

// 741
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        int dp[2*n-1][n+1][n+1];
        memset(dp, 0xf0, sizeof(dp));
        int a[n+1][n+1];
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                a[i][j] = grid[i-1][j-1];
        int j, y;
        int now;
        dp[0][1][1] = a[1][1];
        for (int k=1; k<n*2-1; k++){
            for (int i=1; i<=min(k+1, n); i++){
                for (int x=1; x<=i; x++){
                    if (k-i+2 > n || k-x+2 > n){
                        continue;
                    }
                    j = k + 1 - i + 1;
                    y = k + 1 - x + 1;
                    if (a[i][j] == -1 || a[x][y] == -1){
                        continue;
                    }
                    now = max({dp[k-1][i][x], dp[k-1][i-1][x], dp[k-1][i][x-1], dp[k-1][i-1][x-1]});
                    now += a[i][j];
                    if (i != x)
                        now += a[x][y];
                    dp[k][i][x] = now;
                }
            }
        }
        int ans = max(dp[2*n-2][n][n], 0);
        return ans;
    }
};