题目描述

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

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

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

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

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

样例

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

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

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

限制

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

算法

(动态规划) $O(n^2)$

1. 我们不妨从左上角出发，到右下角。设状态 $f(i, j)$ 表示从左上角到 $(i, j)$ 的最大得分，$g(i ,j)$ 表示在最大得分下的方案数。如果不存在路径，则 $f(i, j) = -1, g(i, j) = 0$。
2. 每次有三种转移，即从左边，左上，和上边转移到当前点。转移时，如果当前最大得分等于另一种转移的最大得分，则累加 $g$ 数组。
3. 最终答案为 $f(n - 1, n - 1), g(n - 1, n - 1)$。

时间复杂度

• 共有 $O(n^2)$ 种状态，每次转移的时间为常数，故时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size();
        vector<vector<int>> f(n, vector<int>(n, -1));
        vector<vector<int>> g(n, vector<int>(n, 0));

        const int dx[3] = {0, -1, -1};
        const int dy[3] = {-1, -1, 0};
        const int mod = 1000000007;

        board[n - 1][n - 1] = '0';
        f[0][0] = 0;
        g[0][0] = 1;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X')
                    continue;
                for (int k = 0; k < 3; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || y < 0 || f[x][y] < 0)
                        continue;

                    if (f[i][j] < f[x][y] + board[i][j] - '0') {
                        f[i][j] = f[x][y] + board[i][j] - '0';
                        g[i][j] = g[x][y];
                    } else if (f[i][j] == f[x][y] + board[i][j] - '0') {
                        g[i][j] = (g[i][j] + g[x][y]) % mod;
                    }
                }
            }

        if (f[n - 1][n - 1] < 0)
            return {0, 0};
        return {f[n - 1][n - 1], g[n - 1][n - 1]};
    }
};