1301. Number of Paths with Max Score

题目信息

题号:

1301

难度:

Hard

主题:

网格、动态规划、路径计数

原题:

LeetCode 1301

重点:

从右下角 S 走到左上角 E,只能向上、向左或左上移动;先最大化经过数字之和,再统计达到最大分数的路径数

题目重述

给定 n x n 字符棋盘,左上角为 E,右下角为 S,数字格表示可获得分数,X 表示障碍。每一步只能向上、向左或左上移动,且不能经过障碍。

返回 [最大分数, 达到该分数的路径数量],路径数对 10^9 + 7 取模。起点和终点本身不计分;若不存在合法路径,返回 [0,0]。

2 <= n <= 100。

自建示例

存在多条路径时先比较分数:

输入:board = ["E12","1X1","21S"]
输出:[4,2]
解释:两条最优路径分别收集 1+1+2 或 2+1+1,最大分数为 4,共两条。

障碍完全阻断时返回零对:

输入:board = ["EX","XS"]
输出:[0,0]
解释:从 S 无法到达 E。