LeetCode 每日一题 ---- 【741.摘樱桃】

741.摘樱桃

方法：动态规划

这是一道动态规划的题目，enmmmm，依旧是做不出来，尤其是看到困难两个标红的字体，就更不想做了，然后是看着答案一点一点顺着思路和题解做的，做完后发现也没有想象中的那么难

从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径，
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发，且速度相同。无论这两人怎么走，在时间相同的情况下，
他们向右走的步数加上向下走的步数之和是一个定值（设为 k）。
设两人的坐标为 (x1,y1)和 (x2,y2)，则 x1+y1=x2+y2=k。
那么当 x1=x2 时，必然有 y1=y2，即两个人到达了同一个格子。
定义状态：f[k][x1][x2]
k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发，到达(n-1, n-1)锁摘到樱桃个数之和
x1，x2分别代表第一个和第二个人的起始横坐标
状态转移方程：
f[k][x1][x2]可以由四种情况转移过来
都往右：f[k][x1][x2] = f[k-1][x1][x2]
A往下，B往右：f[k][x1][x2] = f[k-1][x1-2][x2]
A往右，B往下：f[k][x1][x2] = f[k-1][x1][x2-1]
都往下：f[k][x1][x2] = f[k-1][x1-1][x2-1]
f[k][x1][x2]的最终结果是上述四种情况的最大值，然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案
若x1==x2说明第一个人和第二个人的位置重合了，所以在这种情况下，grid[x1][k-x1]只能加一次

/**
从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径，
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发，且速度相同。无论这两人怎么走，在时间相同的情况下，
他们向右走的步数加上向下走的步数之和是一个定值（设为 k）。
设两人的坐标为 (x1,y1)和 (x2,y2)，则 x1+y1=x2+y2=k。
那么当 x1=x2 时，必然有 y1=y2，即两个人到达了同一个格子。
定义状态：f[k][x1][x2] 
            k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发，到达(n-1, n-1)锁摘到樱桃个数之和
            x1，x2分别代表第一个和第二个人的起始横坐标
状态转移方程：
    f[k][x1][x2]可以由四种情况转移过来
        都往右：f[k][x1][x2] = f[k-1][x1][x2]
        A往下，B往右：f[k][x1][x2] = f[k-1][x1-2][x2]
        A往右，B往下：f[k][x1][x2] = f[k-1][x1][x2-1]
        都往下：f[k][x1][x2] = f[k-1][x1-1][x2-1]
    f[k][x1][x2]的最终结果是上述四种情况的最大值，然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案
    若x1==x2说明第一个人和第二个人的位置重合了，所以在这种情况下，grid[x1][k-x1]只能加一次
 */
class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] f = new int[n * 2 - 1][n][n];
        // 初始化
        for (int i = 0; i < n * 2 - 1; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                Arrays.fill(f[i][j], Integer.MIN_VALUE);
            }
        }
        f[0][0][0] = grid[0][0];
        for (int k = 1; k < n * 2 - 1; k ++ ) {
            // 防止越界
            for (int x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); x1 ++ ) {
                int y1 = k - x1;
                // 荆棘不可越过
                if (grid[x1][y1] == -1) {
                    continue;
                }
                for (int x2 = x1; x2 <= Math.min(k, n - 1); x2 ++ ) {
                    int y2 = k - x2;
                    if (grid[x2][y2] == -1) {
                        continue;
                    }
                    // 都往右
                    int res = f[k - 1][x1][x2];
                    // 往下，往右
                    if (x1 > 0) {
                        res = Math.max(res, f[k - 1][x1 - 1][x2]);
                    }
                    // 往右，往下
                    if (x2 > 0) {
                        res = Math.max(res, f[k - 1][x1][x2 - 1]);
                    }
                    // 都往下
                    if (x1 > 0 && x2 > 0) {
                        res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]);
                    }
                    res += grid[x1][y1];
                    if (x2 != x1) {
                        res += grid[x2][y2];
                    }
                    f[k][x1][x2] = res;
                }
            }
        }
        return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);
    }
}

时间复杂度：
O(n³)

空间复杂度：
O(n²)