[LeetCode] 1301. Number of Paths with Max Score #1301

grandyang · 2019-05-30T16:34:22Z

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 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表示，其他位置可能是数字或者是字符X，其中X表示障碍物，不能通过，而数字表示可以收集的分数，现在让从起点走到终点，并返回两个数字，一个是可以得到的最大分数，另一个是得到该分数的不同路径的个数（需要对一个超大数取余）。博主现在只要一看到说是结果要对一个超大数取余，下意识就会想到是要用动态规划 Dynamic Programming 来做。这道题的每个状态有两个信息，一个是当前的最大得分，另一个是获得该得分的不同路径数，为了简单起见，分别用两个数组 score 和 path 来表示，其中 score[i][j] 表示从 (n-1, n-1) 到 (i, j) 位置可获得的最大分数，path[i][j] 获得 score[i][j] 分数的不同路径个数，将 path[n-1][n-1] 初始化为1。

这道题的本质还是算迷宫遍历的题目，只不过不再是上下左右这四个方向，而是左，上，和左上这三个方向。但整体的思路还是 BFS 遍历的那一套，遍历的方向是从右下角开始，一层一层的向上遍历，最终到达左上角。对于每个遍历到的位置 (i, j)，判断若 path[i][j] 为0，表示没有路径能到达这个位置，直接跳过。否则就遍历其左边，上边，和左上边的位置，若越界了，或者是障碍物X，则直接跳过。否则将该位置的分数取出（注意判断下是否为结束位置E），加上原来位置的分数 score[i][j]，得到总分数 sum。比较一下 sum 和 score[x][y] 的值，若 sum 大，则将 sum 赋值给 score[x][y]，并且将 path[i][j] 赋值给 path[x][y]，这不难理解吧，因为小的分数的路径数就没用了，所以可以直接覆盖掉。而若 sum 和 score[x][y] 相等的话，则表示有了不同的路径，需要将 path[i][j] 加到 path[x][y] 中，记得要对超大数取余，这样更新完成了之后，最后的结果就分别存在 score[0][0] 和 path[0][0] 之中了，参见代码如下：

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size(), M = 1e9 + 7;
        vector<vector<int>> score(n, vector<int>(n)), path = score;
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {-1, -1}};
        path[n - 1][n - 1] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (path[i][j] == 0) continue;
                for (auto dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x < 0 || y < 0 || board[x][y] == 'X') continue;
                    int sum = score[i][j];
                    if (board[x][y] != 'E') sum += board[x][y] - '0';
                    if (sum > score[x][y]) {
                        score[x][y] = sum;
                        path[x][y] = path[i][j];
                    } else if (sum == score[x][y]) {
                        path[x][y] = (path[x][y] + path[i][j]) % M;
                    }
                }
            }
        }
        return {score[0][0], path[0][0]};
    }
};

Github 同步地址:

#1301

参考资料：

https://leetcode.com/problems/number-of-paths-with-max-score/

https://leetcode.com/problems/number-of-paths-with-max-score/discuss/463539/C%2B%2B-DP

https://leetcode.com/problems/number-of-paths-with-max-score/discuss/463196/Java-DP-Solution-Clean-code-O(m*n)

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~