1301. Number of Paths with Max Score¶
题目信息¶
- 题号:
1301
- 难度:
Hard
- 主题:
网格、动态规划、路径计数
- 原题:
- 重点:
从右下角
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。