算法思路

该题与LeetCode 741. 摘樱桃属于一类题，均属于动态规划中的数字三角形模型， DP模型与AcWing 275.传纸条一模一样，思路也相同。

该题与741题不同点在于两个人起点不同，走的方向也不一样。由于该题的特殊性，每个人只能向下，左下，右下三个方向移动，因此每次移动，横坐标必然会增加，且最后结束时是两个人同时到达最下一行。所以在移动过程中保证了两个人的横坐标相同，列坐标不同，我们的DP分析如下：

状态表示：
f[k][i][j]表示走到第k行，第一个人的纵坐标为i，第二个人纵坐标为j的所有方案

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

状态转移：
状态转移方程中，每一个转移第一维必然是从k - 1行转移过来，而对于第二维和第三维，每一种有3中可能，因此可以用3 * 3的循环来表示每种转移。

C ++代码

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> f(n, vector<vector<int>> (m, vector<int> (m, -1)));

        f[0][0][m - 1] = grid[0][0] + grid[0][m - 1]; //开始状态

        int res = 0;
        for (int k = 1; k < n; k ++) //从第二行开始循环
            for (int i = 0; i < m; i ++) 
                for (int j = 0; j < m; j ++)
                    for (int a = i - 1; a <= i + 1; a ++)
                        for (int b = j - 1; b <= j + 1; b ++)
                        {
                            if (a < 0 || a >= m || b < 0 || b >= m) continue; //越界
                            int t = f[k - 1][a][b];
                            if (t < 0) continue; //不合法

                            if (i == j) f[k][i][j] = max(f[k][i][j], t + grid[k][i]); //重合时只算一次分值
                            else f[k][i][j] = max(f[k][i][j], t + grid[k][i] + grid[k][j]);
                            res = max(res, f[k][i][j]);
                        }

        return res;
    }
};