1463. Cherry Pickup II

O(mnn) time O(mnn) space
f[i][l][r]表示从行i两个robot从列l和r开始分别往下能pickup多少
初始f[0][0][n - 1]表示两个robot分别从第0行第0和第n - 1列开始往下pickup
f[i][l][r] = max{f[i - 1][c1][c2]} + grid[i][l] if l == r
f[i][l][r] = max{f[i - 1][c1][c2]} + grid[i][l] + grid[i][r] elsewise
where c1 ~ [l - 1 : l + 1] and c2 ~ [r - 1 : r + 1]
因为都是非负数所以用f[i][l][r]更新res即可

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int m = size(grid), n = size(grid[0]), res = 0;
        vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(n)));
        f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];
        for (int i = 1; i < m; ++i) {
            for (int l = 0; l < min(n, i + 1); ++l) {
                for (int r = max(0, n - i - 1); r < n; ++r) {
                    int t = 0;
                    for (int c1 = max(0, l - 1); c1 <= min(n - 1, l + 1); ++c1) {
                        for (int c2 = max(0, r - 1); c2 <= min(n - 1, r + 1); ++c2) {
                            t = max(t, f[i - 1][c1][c2]);
                        }
                    }
                    if (l == r) {
                        f[i][l][r] = t + grid[i][l];
                    } else {
                        f[i][l][r] = t + grid[i][l] + grid[i][r];
                    }
                    res = max(res, f[i][l][r]);
                }
            }
        }
        return res;
    }
};