1301 Number of Paths with Max Score 最大得分的路径数目

Description:

You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.

You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.

Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.

In case there is no path, return [0, 0].

Example:

Example 1:

Input: board = ["E23","2X2","12S"]
Output: [7,1]

Example 2:

Input: board = ["E12","1X1","21S"]
Output: [4,2]

Example 3:

Input: board = ["E11","XXX","11S"]
Output: [0,0]

Constraints:

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

题目描述：

给你一个正方形字符数组 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

思路：

动态规划
等效为从左上角出发到右下角
将终点的值记为 ‘0’
设 dp[i][j] 表示到达 board[i - 1][j - 1] 的得分, count[i][j] 表示到达 board[i - 1][j - 1] 取得最大得分的方案数
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + int(board[i][j]), if board[i][j] != 'X', 并且能够到达 dp[i][j]
也就是说 count[i][j], count[i - 1][j], count[i][j - 1] 至少有一个不为 0
令 cur = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
则 if dp[i - 1][j - 1] == cur, count[i][j] += count[i - 1][j - 1], 表示可以从左上方到达该格
其他两个方向以此类推
时间复杂度为 O(n ^ 2), 空间复杂度为 O(n ^ 2)

代码:

C++:

class Solution 
{
public:
    vector<int> pathsWithMaxScore(vector<string>& board) 
    {
        int n = board.size(), mod = 1e9 + 7;
        board.back().back() = '0';
        vector<vector<int>> dp(n + 1 , vector<int>(n + 1)), count(n + 1 , vector<int>(n + 1));
        count[1][1] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (board[i - 1][j - 1] != 'X' and (count[i - 1][j - 1] or count[i - 1][j] or count[i][j - 1]))
                {
                    int cur = max({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
                    dp[i][j] = (cur + board[i - 1][j - 1] - '0') % mod;
                    if (dp[i - 1][j - 1] == cur) count[i][j] = (count[i][j] + count[i - 1][j - 1]) % mod;
                    if (dp[i][j - 1] == cur) count[i][j] = (count[i][j] + count[i][j - 1]) % mod;
                    if (dp[i - 1][j] == cur) count[i][j] = (count[i][j] + count[i - 1][j]) % mod;
                }
            }
        }
        return {dp.back().back(), count.back().back()};
    }
};

Java:

class Solution {
    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size(), dp[][] = new int[n + 1][n + 1], count[][] = new int[n + 1][n + 1], mod = 1_000_000_007;
        count[1][1] = 1;
        board.set(n - 1, board.get(n - 1).substring(0, n - 1) + "0");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (board.get(i - 1).charAt(j - 1) != 'X' && (count[i - 1][j - 1] > 0 || count[i - 1][j] > 0 || count[i][j - 1] > 0)) {
                    int cur = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1]));
                    dp[i][j] = (cur + board.get(i - 1).charAt(j - 1) - '0') % mod;
                    if (dp[i - 1][j - 1] == cur) count[i][j] = (count[i][j] + count[i - 1][j - 1]) % mod;
                    if (dp[i][j - 1] == cur) count[i][j] = (count[i][j] + count[i][j - 1]) % mod;
                    if (dp[i - 1][j] == cur) count[i][j] = (count[i][j] + count[i - 1][j]) % mod;
                }
            }
        }
        return new int[]{dp[n][n], count[n][n]};
    }
}

Python:

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        n = len(board)
        dp, count, mod = [[0] * (n + 1) for _ in range(n + 1)], [[0] * (n + 1) for _ in range(n + 1)], 10 ** 9 + 7
        count[1][1], board[-1] = 1, board[-1][:-1] + '0'
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if board[i - 1][j - 1] != 'X' and (count[i - 1][j - 1] or count[i][j - 1] or count[i - 1][j]):
                    dp[i][j] = (cur := max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])) + int(board[i - 1][j - 1])
                    count[i][j] += (count[i - 1][j - 1] if dp[i - 1][j - 1] == cur else 0) + (count[i][j - 1] if dp[i][j - 1] == cur else 0) + (count[i - 1][j] if dp[i - 1][j] == cur else 0)
        return [dp[-1][-1] % mod, count[-1][-1] % mod]