算法思路

该题属于动态规划中的数字三角形模型， DP模型与AcWing 275.传纸条一模一样，思路也相同。虽然要求是从左上角走到右下角，再从右下角走回左上角，但是我们可以假设是两个人从左上角同时分别向右下角走。又因为每个格子的东西只能被取一次，所以当两个人的路线重合时，我们只保证其中一个人取到东西。

状态表示：
f[k][i][j]表示一共走了k步，第一个人的横坐标为i，第二个人横坐标为j的所有方案

状态属性：
表示的是此时两个人走到各自格子时，所取得的分值和最大值。

状态转移：
因为题目要求只能往下走和往右走，所以对于走到的每一个格子来说，它可能来自的方向就是上面或左边。由于是两个格子同时的状态转移，所以状态转移方程为4个，具体转移方程见代码。

C ++代码

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<vector<int>>> f(n * 2, vector<vector<int>> (n, vector<int> (n, INT_MIN)));

        f[0][0][0] = grid[0][0]; //在起点
        for (int k = 1; k <= n * 2 - 2; k ++) //步数从1开始
            for (int i1 = 0; i1 < n; i1 ++) //第一个人的横坐标
                for (int i2 = 0; i2 < n; i2 ++) //第二个人的横坐标
                { 
                    int j1 = k - i1, j2 = k - i2; //分别纵坐标
                    if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n) continue; //越界
                    if (grid[i1][j1] == -1 ||grid[i2][j2] == -1) continue; //障碍物

                    int t = grid[i1][j1]; //取得该格子
                    if (i1 != i2) t += grid[i2][j2]; //没有重合

                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1][i2] + t);
                    if (i1) x = max(x, f[k -1][i1 - 1][i2] + t);
                    if (i2) x = max(x, f[k -1][i1][i2 - 1] + t);
                    if (i1 && i2) x = max(x, f[k -1][i1 - 1][i2 - 1] + t);
                }

        return max(0, f[n * 2 - 2][n - 1][n - 1]); //因为没有合法路径
    }
};