最大路径和问题(摘樱桃问题)


最大路径和问题(摘樱桃问题)

作者:Grey

原文地址: 最大路径和问题(摘樱桃问题)

题目链接

LeetCode 741. 摘樱桃

主要思路

本题的难点在于尝试,如何模拟一来一回的情况,我们可以这样做,定义两个小人,两个人都从(0,0)位置出发,到右下角位置,每人同时选择不同的下一步,如果两个小人跳到了同一个位置,只计算一份。由于两个小人是同时走,而且每次只走一步,所以,两个小人一定是同时到达右下角的,两个小人一路收集的樱桃数量,就是一来一回收集的数量。

我们可以写出第一个尝试版本,定义递归函数

int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2)

递归函数的含义表示,第一个小人从(x1,y1)开始到右下角,第二个小人从(x2,y2)开始到右下角,获取到的最大值是多少。所以p(matrix, m, n, 0, 0, 0, 0)就是我们需要的答案。

接下来考虑base case,即:两个小人都到达了右下角,由于题目已经说了,右下角的值一定不是-1,所以,可以获得一份樱桃数量。

        if (x1 == m - 1 && y1 == n - 1) {
            // 已经到了最右下角了
            // 隐含条件:另外一个点也一定到达右下角
            // 获得一份樱桃数
            return matrix[x1][y1];
        }

接下来就是普遍尝试,分别可以分成如下四种情况:

情况1:第一个小人往下,第二个小人往右。

情况2:第一个小人往下,第二个小人往下。

情况3:第一个小人往右,第二个小人往下。

情况4:第一个小人往右,第二个小人往右。

但是在走上述任何分支的时候,记得要满足两个条件

第一个条件,不能越界

第二个条件,下一个要走的位置不能是-1,因为题目说到,-1是不能走的位置。

        int next = -1;
        // 下,下
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
        }
        // 下,右
        if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
        }
        // 右,下
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
        }
        // 右,右
        if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
        }

经过上述四个分支,如果next的值还是-1,说明无路可走,返回-1

        if (next == -1) {
            return -1;
        }

如果next不等于-1,说明有可以走的路径,那么继续判断两个小人是否在同一位置,如果在同一个位置,则只收集一份樱桃,如果不在同一个位置,收集两个小人所在位置的樱桃之和。

        if (x1 == x2) {
            // 到达同一个位置,只取一个值
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][y2];

注:判断同一个位置,只需要一个维度上的坐标相等即可

完整代码

    public static int cherryPickup1(int[][] matrix) {
        return Math.max(0, p(matrix, matrix.length, matrix[0].length, 0, 0, 0, 0));
    }

    // 定义两个小人,两个人都从(0,0)位置出发,到右下角位置,每人同时选择不同的下一步,如果两个小人跳到了同一个位置,只计算一份。
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2) {
        if (x1 == m - 1 && y1 == n - 1) {
            // 已经到了最右下角了
            // 隐含条件:另外一个点也一定到达右下角
            // 获得一份樱桃数
            return matrix[x1][y1];
        }

        int next = -1;
        // 下,下
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
        }
        // 下,右
        if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
        }
        // 右,下
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
        }
        // 右,右
        if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
        }
        if (next == -1) {
            return -1;
        }
        if (x1 == x2) {
            // 到达同一个位置,只取一个值
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][y2];
    }

这个解法在 LeetCode 上直接超时。

在上述尝试的基础上,我们可以做进一步的优化,递归函数现在是四个可变参数,根据我们的设计,其实可以得到如下公式

x1 + y1 = x2 + y2

那么我们可以将递归函数省略一个参数y2,因为

y2 = x1 + y1 - x2

上述递归方法我们可以修改为

// 省略y2参数
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2) {
        if (x1 == m - 1 && y1 == n - 1) {
            // 已经到了最右下角了
            // 隐含条件:另外一个点也一定到达右下角
            // 获得一份樱桃数
            return matrix[x1][y1];
        }

        int next = -1;
        // 下,下
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1), next);
        }
        // 下,右
        if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2), next);
        }
        // 右,下
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1), next);
        }
        // 右,右
        if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2), next);
        }
        if (next == -1) {
            return -1;
        }
        if (x1 == x2) {
            // 到达同一个位置,只取一个值
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
    }
    public static int getY2(int x1, int y1, int x2) {
        return x1 + y1 - x2;
    }

我们可以做进一步的优化,由于三个可变参数的范围分别是[0...m-1][0...n-1][0...m-1],那么我们可以设置三维dp,将所有递归结果缓存起来

int[][][] dp = new int[m][n][m];

三维dp的所有位置初始值设置为Integer.MIN_VALUE,在递归方法中,将这个三维表作为缓存带入参数中,每次递归过程中,先从dp表中拿值,如果值不为Integer.MIN_VALUE,说明这个过程算过,直接取值即可。

    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
        if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
            // 说明这个过程曾经算过,直接从缓存中取值即可
            return dp[x1][y1][x2];
        }
    }

然后在每次递归过程中,将答案存入缓存,完整代码如下

    // 动态规划
    // 三维表
    public static int cherryPickup(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][][] dp = new int[m][n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    // 初始值设置为Integer.MIN_VALUE,只要不等于Integer.MIN_VALUE,就说明递归过程已经算过了
                    dp[i][j][k] = Integer.MIN_VALUE;
                }
            }
        }
        return Math.max(0, p(matrix, m, n, 0, 0, 0, dp));
    }

    // 定义两个小人,两个人都从(0,0)位置出发,到右下角位置,每人同时选择不同的下一步,如果两个小人跳到了同一个位置,只计算一份。
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
        if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
            // 说明这个过程曾经算过,直接从缓存中取值即可
            return dp[x1][y1][x2];
        }
        if (x1 == m - 1 && y1 == n - 1) {
            // 已经到了最右下角了
            // 隐含条件:另外一个点也一定到达右下角
            // 获得一份樱桃数
            dp[x1][y1][x2] = matrix[x1][y1];
            return matrix[x1][y1];
        }

        int next = -1;
        // 下,下
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, dp), next);
        }
        // 下,右
        if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, dp), next);
        }
        // 右,下
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, dp), next);
        }
        // 右,右
        if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, dp), next);
        }
        if (next == -1) {
            dp[x1][y1][x2] = -1;
            return -1;
        }
        if (x1 == x2) {
            // 到达同一个位置,只取一个值
            // 将答案存入缓存
            dp[x1][y1][x2] = next + matrix[x1][y1];
            return dp[x1][y1][x2];
        }
        // 将答案存入缓存
        dp[x1][y1][x2] = next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
        return dp[x1][y1][x2];
    }

    public static int getY2(int x1, int y1, int x2) {
        return x1 + y1 - x2;
    }

时间复杂度O(m*n*m),LeetCode 中直接AC。

更多

算法和数据结构笔记

原创文章,作者:端木书台,如若转载,请注明出处:https://blog.ytso.com/270489.html

(0)
上一篇 2022年6月27日
下一篇 2022年6月27日

相关推荐

发表回复

登录后才能评论