741. Cherry Pickup

这道题的关键点是想成两个人同时从[0, 0]开始到[r1, c1]和[r2, c2]一共最多采多少cherry，每一步两个人只能向右或向下，这样就有四种可能
greedy是一定不行的，反例如下

1 1 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 1
1 0 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 1 1 1 1

dp O(n³) time O(n²) space
在第s步，f[i][j]表示两个人从grid[0][0]到grid[i][s - i]和grid[j][s - j]一共最多采多少cherry
正向，需要一个temp

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> f(n, vector<int>(n, INT_MIN));
        f[0][0] = grid[0][0]; // 因为从第一步开始算起，所以f[0][0]要初始化
        for (int s = 1; s <= 2 * n - 2; ++s) { // 一共需要走s步，每一步两个人分别在grid[i][s - i]和grid[j][s - j]
            vector<vector<int>> t(n, vector<int>(n, INT_MIN));
            int b = max(0, s - n + 1), e = min(s + 1, n); // 由0 <= s - i < n推出
            for (int i = b; i < e; ++i) {
                if (grid[i][s - i] == -1) continue;
                for (int j = b; j < e; ++j) {
                    if (grid[j][s - j] == -1) continue;
                    int v = f[i][j];
                    if (i > 0) {
                        v = max(v, f[i - 1][j]);
                    }
                    if (j > 0) {
                        v = max(v, f[i][j - 1]);
                    }
                    if (i > 0 && j > 0) {
                        v = max(v, f[i - 1][j - 1]);
                    }
                    v += grid[i][s - i] + (i == j ? 0 : grid[j][s - j]); // 如果i跟j在同一行则也必在同一列，因为走的步数相同，则只能有一个人取cherry
                    t[i][j] = v;
                }
            }
            f = t;
        }
        return max(0, f[n - 1][n - 1]);
    }
};

逆向，进一步优化，不需要temp

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> f(n, vector<int>(n, INT_MIN));
        f[0][0] = grid[0][0];
        for (int s = 1; s <= 2 * n - 2; ++s) {
            int b = max(0, s - n + 1), e = min(s + 1, n);
            for (int i = e - 1; i >= b; --i) {
                for (int j = e - 1; j >= b; --j) {
                    if (grid[i][s - i] == -1 || grid[j][s - j] == -1) {
                        f[i][j] = INT_MIN; // 因为是逆向做，所以需要对非法值也进行修改
                        continue;
                    }
                    int v = f[i][j];
                    if (i > 0) {
                        v = max(v, f[i - 1][j]);
                    }
                    if (j > 0) {
                        v = max(v, f[i][j - 1]);
                    }
                    if (i > 0 && j > 0) {
                        v = max(v, f[i - 1][j - 1]);
                    }
                    v += grid[i][s - i] + (i == j ? 0 : grid[j][s - j]);
                    f[i][j] = v;
                }
            }
        }
        return max(0, f[n - 1][n - 1]);
    }
};

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> f(n, vector<int>(n, INT_MIN));
        f[0][0] = grid[0][0];
        for (int s = 1; s <= 2 * n - 2; ++s) {
            vector<vector<int>> t(n, vector<int>(n, INT_MIN));
            for (int i = 0; i <= s && i < n; ++i) {
                for (int j = 0; j <= s && j < n; ++j) {
                    if (grid[i][s - i] == -1 || grid[j][s - j] == -1) continue;
                    int v = f[i][j];
                    if (i > 0) {
                        v = max(v, f[i - 1][j]);
                    }
                    if (j > 0) {
                        v = max(v, f[i][j - 1]);
                    }
                    if (i > 0 && j > 0) {
                        v = max(v, f[i - 1][j - 1]);
                    }
                    v += grid[i][s - i] + (i == j ? 0 : grid[j][s - j]);
                    t[i][j] = v;
                }
            }
            f.swap(t);
        }
        return max(0, f[n - 1][n - 1]);
    }
};

memo+dp O(n³) time O(n³) space
用递归做比较实际

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<vector<int>>> cache(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        return max(0, dfs(grid, 0, 0, 0, cache));
    }

    int dfs(const vector<vector<int>> &grid, int r1, int c1, int r2, vector<vector<vector<int>>> &cache) {
        int n = grid.size();
        int c2 = r1 + c1 - r2;
        if (r1 == n || c1 == n || r2 == n || c2 == n || grid[r1][c1] == -1 || grid[r2][c2] == -1) return INT_MIN;
        if (r1 == n - 1 && c1 == n - 1) return grid[r1][c1]; // 终止条件，再往下递归结果是错的
        if (cache[r1][c1][r2] != INT_MIN) return cache[r1][c1][r2];
        int res = grid[r1][c1] + (r1 == r2 ? 0 : grid[r2][c2]);
        res += max({dfs(grid, r1 + 1, c1, r2 + 1, cache),
                    dfs(grid, r1, c1 + 1, r2, cache),
                    dfs(grid, r1 + 1, c1, r2, cache),
                    dfs(grid, r1, c1 + 1, r2 + 1, cache)});
        return cache[r1][c1][r2] = res;
    }
};