1463.摘樱桃II

方法：动态规划（递推）

昨天是摘樱桃I，今天是II，与昨天的区别主要在于，今天的是两个人分别从左上角和右上角出发，且只能往下或右下和左下移动，求都移动到最后一排所能摘到樱桃的数量。

直接附上题解吧：
作者：灵茶山艾府
链接：https://leetcode.cn/problems/cherry-pickup-ii/solutions/2768158/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-i70v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int cherryPickup(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] f = new int[m + 1][n + 2][n + 2];
        for (int i = m - 1; i >= 0; i -- ) {
            for (int j = 0; j < Math.min(n, i + 1); j ++ ) {
                for (int k = Math.max(j + 1, n - 1 - i); k < n; k ++ ) {
                    f[i][j + 1][k + 1] = max(
                        f[i + 1][j][k], f[i + 1][j][k + 1], f[i + 1][j][k + 2],
                        f[i + 1][j + 1][k], f[i + 1][j + 1][k + 1], f[i + 1][j + 1][k + 2],
                        f[i + 1][j + 2][k], f[i + 1][j + 2][k + 1], f[i + 1][j + 2][k + 2]
                    ) + grid[i][j] + grid[i][k];
                }
            }
        }
        return f[0][1][n];
    }
    private int max(int x, int... y) {
        for (int v : y) {
            x = Math.max(x, v);
        }
        return x;
    }
}

时间复杂度：
O(nm²)

空间复杂度：
O(nm²)