1301：最大得分的路径数目（1853 分）

Ian

2019-12-28 约 439 字预计阅读 1 分钟次阅读

力扣第 16 场双周赛第 4 题

题目

给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的「得分」定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是「得分」的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

示例 1：

输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：

输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：

输入：board = ["E11","XXX","11S"]
输出：[0,0]

提示：

2 <= board.length == board[i].length <= 100

分析

递推时同时保存最大得分和对应的方案数即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        mod = 10**9+7
        n = len(board)
        f = [[-inf]*(n+1) for _ in range(n+1)]
        g = [[0]*(n+1) for _ in range(n+1)]
        f[-1][-1] = 0
        g[-1][-1] = 1
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):
                c = board[i][j]
                if c=='X':
                    continue
                a,b = -inf,0
                for x,y in [(i+1,j),(i,j+1),(i+1,j+1)]:
                    if f[x][y]>a:
                        a,b = f[x][y],g[x][y]
                    elif f[x][y]==a:
                        b += g[x][y]
                f[i][j] = a+(0 if c in 'SE' else int(c))
                g[i][j] = b%mod
        return [max(0,f[0][0]),g[0][0]]

71 ms

目录

1301：最大得分的路径数目（1853 分）

题目

分析

解答