LEETCODE 1301. Number of Paths with Max Score 解题思路分析

题目大意：

最大得分的路径数目

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

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1301

解题思路分析：

虽然题目给出的是一个字符串列表，但实际上将其想像成为一个2位数组（棋盘）更好理解。本题需要解决2个问题，最大得分和最大得分的所有方案数。这是一道标准的动态规划DP题目。我们定义2个dp数组，max[i][j]代表到达坐标(i, j)时的最大得分，count[i][j]代表到达坐标(i, j)时能够取得最大得分的路线数量。由于只能向上方，左方，以及左上方3个方向移动，因此对于任意一点，他能得到的最大分数取决于能够达到此点路径上之前和最大的那一条（下方，右方以及右下方）：

max[i][j] = max(max[i+1][j],max[i][j+1],max[i+1][j+1]) + value(i, j);

另外，对于当前点能够取得最大得分的路径数量，要看哪些路径能够取得最大得分，将这些路径相加即是当前节点上最大得分的路径数量：

int maxCount=0;
if(max[i+1][j+1]==maxValue) maxCount = (maxCount+count[r+1][c+1]);
if(max[i][j+1]==maxValue) maxCount = (maxCount+count[r][c+1]);
if(max[i+1][j]==maxValue) maxCount = (maxCount+count[r+1][c]);
count[i][j]=maxCount;

DP的起点是右下角，初始时，矩阵的下边与右边上的点均只存在一种移动方式，下边上的任意一点只能从其右方到达，右边上的每一个点只能通过其下方到达。

最终，max[0][0]与count[0][0]即为返回结果

实现代码：

public int[] pathsWithMaxScore(List<String> board) {
    int mod=1000000007;
    int row=board.size(); // 行数
    int col=board.get(0).length(); // 列数
    int[][] max=new int[row][col]; // dp数组，当前点的最大和
    max[row-1][col-1]=1; // 起点默认为1。（为了区别其他的0）
    int[][] count=new int[row][col]; // dp数组，当前点最大和的方案数
    count[row-1][col-1]=1; // 起点默认为1。
    // dp初始状态，初始化矩阵右边
    for(int r=row-2;r>=0;r--){
        // 当前字符
        char current=board.get(r).charAt(col-1);
        // 如果是障碍物，退出
        if(current=='X') break;
        // 取得当前数值
        int value=current-'0';
        // 当前点的和等于下方一格的和加上当前数值
        max[r][col-1] = max[r+1][col-1]+value;
        // 当前点的最大方案数为1
        count[r][col-1]=1;
    }
    // dp初始状态，初始化矩阵下边
    for(int c=col-2;c>=0;c--){
        // 当前字符
        char current=board.get(row-1).charAt(c);
        // 如果是障碍物，退出
        if(current=='X') break;
        // 取得当前数值
        int value=current-'0';
        // 当前点的和等于右方一格的和加上当前数值
        max[row-1][c] = max[row-1][c+1]+value;
        // 当前点的最大方案数为1
        count[row-1][c]=1;
    }
    // 从右下方开始循环每一个点，动态规划出最优解
    for(int r=row-2;r>=0;r--){
        char[] arr=board.get(r).toCharArray();
        for(int c=col-2;c>=0;c--){
            // 当前字符
            char current=arr[c];
            // 如果是障碍物，继续
            if(current=='X') continue;
            // 如果是结束位置，当前点可以看做是0
            if(current=='E') current='0';
            // 当前点数值
            int value=current-'0';
            // 取得可以到达当前点的3个点的最大值
            int maxValue=Math.max(max[r+1][c+1],Math.max(max[r+1][c],max[r][c+1]));
            // 如果最大值为0，说明3个点都是障碍物，没有路线能够到达当前点。
            if(maxValue==0) continue;
            // 将最大值加上当前值，存入当前dp数组
            max[r][c] = maxValue+value;
            // 计算最大方案数
            int maxCount=0;
            // 如果右下点等于最大值，最大方案数加上右下方案数
            if(max[r+1][c+1]==maxValue) maxCount= (maxCount+count[r+1][c+1])%mod;
            // 如果下点等于最大值，最大方案数加上下方案数
            if(max[r][c+1]==maxValue) maxCount= (maxCount+count[r][c+1])%mod;
            // 如果右点等于最大值，最大方案数加上右方案数
            if(max[r+1][c]==maxValue) maxCount= (maxCount+count[r+1][c])%mod;
            count[r][c]=maxCount;
        }
    }
    // 这里注意一下，由于初始时，start点的max设置为1，这里需要减去1
    if(max[0][0]>0) max[0][0]--;
    return new int[]{max[0][0], count[0][0]};
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 69.82% of Java online submissions for Number of Paths with Max Score.

Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Number of Paths with Max Score.