经典算法题之摘樱桃（一）

我们先来看题目描述给你一个 n x n 的网格 grid 代表一块樱桃地每个格子由以下三种数字的一种来表示0 表示这个格子是空的所以你可以穿过它。1 表示这个格子里装着一个樱桃你可以摘到樱桃然后穿过它。-1 表示这个格子里有荆棘挡着你的路。请你统计并返回在遵守下列规则的情况下能摘到的最多樱桃数从位置 (0 , 0) 出发最后到达 (n - 1 , n - 1) 只能向下或向右走并且只能穿越有效的格子即只可以穿过值为 0 或者 1 的格子当到达 (n - 1 , n - 1) 后你要继续走直到返回到 (0 , 0) 只能向上或向左走并且只能穿越有效的格子当你经过一个格子且这个格子包含一个樱桃时你将摘到樱桃并且这个格子会变成空的值变为 0 如果在 (0 , 0) 和 (n - 1 , n - 1) 之间不存在一条可经过的路径则无法摘到任何一个樱桃。示例 1输入grid [[0,1,-1],[1,0,-1],[1,1,1]] 输出5 解释玩家从 (0, 0) 出发向下、向下、向右、向右移动至 (2, 2) 。 在这一次行程中捡到 4 个樱桃矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。 然后玩家向左、向上、向上、向左返回起点再捡到 1 个樱桃。 总共捡到 5 个樱桃这是最大可能值。示例 2输入grid [[1,1,-1],[1,-1,1],[-1,1,1]] 输出0提示n grid.lengthn grid[i].length1 n 50grid[i][j] 为 -1 、0 或 1grid[0][0] ! -1grid[n - 1][n - 1] ! -1