1463. Cherry Pickup II

题目信息

题号:

1463

难度:

Hard

主题:

矩阵、动态规划、双机器人

原题:

LeetCode 1463

重点:

两个机器人从首行两端出发,每行各向左下、正下或右下移动;同格樱桃只计一次

题目重述

给定 rows x cols 矩阵 grid,每格表示樱桃数量。机器人一从 (0,0) 出发,机器人二从 (0,cols-1) 出发。

每到下一行,机器人列坐标可以变化 -1、0 或 1,且不能越界。两机器人经过的格子樱桃均被收集;若同时到达同一格,只收集一次。请返回到达最后一行时最多能收集的樱桃数。

2 <= grid.length, grid[i].length <= 70,0 <= grid[i][j] <= 100。

自建示例

两个机器人可以在同一行选择不同高价值格:

输入:grid = [[1,2],[3,4]]
输出:10
解释:首行收集 1 + 2,第二行分别到达 3 和 4,总计 10。

所有格子为零时结果为零:

输入:grid = [[0,0],[0,0]]
输出:0
解释:无论如何移动都没有樱桃可收集。