X

LEETCODE 1463. Cherry Pickup II 解题思路分析

题目大意:

摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃,机器人 1 从左上角格子 (0,0) 出发,机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则,返回两个机器人能收集的最多樱桃数目:

  • 从格子 (i,j) 出发,机器人可以移动到格子 (i+1, j-1),(i+1, j) 或者 (i+1, j+1) 。
  • 当一个机器人经过某个格子时,它会把该格子内所有的樱桃都摘走,然后这个位置会变成空格子,即没有樱桃的格子。
  • 当两个机器人同时到达同一个格子时,它们中只有一个可以摘到樱桃。
  • 两个机器人在任意时刻都不能移动到 grid 外面。
  • 两个机器人最后都要到达 grid 最底下一行。

示例 1:

输入:grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出:24
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为: 12 + 12 = 24 。

示例 2:

输入:grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出:28
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为: 17 + 11 = 28 。

示例 3:

输入:grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出:22

示例 4:

输入:grid = [[1,1],[1,1]]
输出:4

提示:

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1463

解题思路分析:

类似这种每一步都有很多种选择,并且需要在多种选择中挑选出最优解的题目,绝大情况下是需要采用动态规划思路来解题的。本题就是一个经典的案例。由于我个人更青睐于使用递归加记忆数组的方式解DP题目,所以本题也会使用该方式来做讲解。

我们创建一个递归函数,参数中传入两个机器人当前的坐标,初始值为(0,0)与(0, cols-1)两点。每一步递归中,先收集两个机器人当前所在位置上的樱桃(注意如果两个机器人位于同一点时,只收一次)。然后让两个机器人同时向下一行迈出一格,因为每个机器人都各有3种选择(左下,正下或者右下),因此两个机器人同时移动一步后,理论上共存在9种可能。我们除去越界的选择外,循环剩下的每种选择,将机器人的位置更新后传入递归函数。循环中递归函数返回值中的最大值即是当前最优解,最优解加上本层递归收集到的樱桃数即是本层递归的返回值。

最后再来考虑记忆数组,本题递归函数中存在4个变量,即两个机器人的横纵坐标,因此我们需要建立一个4维数组来记录当前递归函数的解。另外这里存在一个可以优化的地方,因为两个机器人不论如何移动,他们始终保持在同一行,因此我们可以将数组降维至3维,即横坐标与两个机器人所在的纵坐标。

如果你仍然无法理解我上面的逻辑,那么说明你对dp或是递归还没有深入的理解。强烈建议你去参考一下我之前总结过的文章:

LEETCODE常见算法之动态规划DP超详细白话讲解(上)

LEETCODE常见算法之动态规划DP超详细白话讲解(下)

实现代码:

int[][] dirs=new int[][]{{1,-1},{1,0},{1,1}}; // 可移动的方向
Integer[][][] memo; // 记忆数组
public int cherryPickup(int[][] grid) {
    // 初始化记忆数组
    memo=new Integer[grid.length][grid[0].length][grid[0].length];
     // 递归求解
    return help(grid,0,0,grid[0].length-1);
}
// grid:地图
// r1:当前行
// c1:机器人1所在列
// c2:机器人2所在列
// 返回值:从当前位置到最后一行间能采摘到最多的樱桃数
int help(int[][] grid,int r1,int c1,int c2){
    // 如果记忆数组中存在当前解,返回记忆数组中的值
    if(memo[r1][c1][c2]!=null) return memo[r1][c1][c2];
    // 采摘机器人1所在位置的樱桃,并累加至返回结果
    int res=grid[r1][c1];
    // 如果两个机器人不在同一位置,采摘第二个机器人所在位置的樱桃
    if(c1!=c2) res+=grid[r1][c2];
    int max=0; // 最优解
    for(int[] d1 : dirs){ // 循环第一个机器人下一步的三种选择
        int row1=r1+d1[0],col1=c1+d1[1]; // 机器人1下一步坐标
        if(row1==grid.length) break; // 如果行越界,退出
        if(col1<0||col1==grid[0].length) continue; // 如果列越界,继续
        for(int[] d2 : dirs){ // 循环第二个机器人下一步的三种选择
            int col2=c2+d2[1]; // 机器人2下一步坐标
            if(col2<0||col2==grid[0].length) continue; // 如果列越界,继续
            // 利用两个机器人下一步坐标,递归至子函数
            // 并利用递归返回值更新最大值
            max=Math.max(max,help(grid,row1,col1,col2));
        }
    }
    res+=max; // 返回结果加上最大值
    memo[r1][c1][c2]=res; // 将返回结果计入记忆数组
    return res;
}

本题解法执行时间为17ms

Runtime: 17 ms, faster than 76.53% of Java online submissions for Cherry Pickup II.

Memory Usage: 39.1 MB, less than 100.00% of Java online submissions for Cherry Pickup II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1463-cherry-pickup-ii-解题思路分析/
Categories: leetcode
kwantong: