最大得分的路径数目

题目

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

思路

定义dp[i][j]表示位置(i,j)的最大得分,则dp[i][j]=max(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])。

则dp[0][0]就是答案。m为board的长度,n为每一个字符串的长度。dp[m-1][n-1]就是S的位置的最大得分。

而m-1行的状态,只能从dp[i][j+1]转移而来,n-1列的状态,只能从dp[i+1][j]转移而来。题目还要求最大

得分的路径数,对于dp[i+1][j],dp[i][j+1],dp[i+1][j+1],假设它们的路径数分别为2,2,3,dp[i+1][j]

为最大值,同时dp[i+1][j]=dp[i][j+1],则dp[i][j]的路径数为2+2种。用一个数组来表示最大得分和其路径数

dp[i][j][0]表示最大得分,dp[i][j][1]表示路径数。每次算出最大得分的时候,再判断一下是否有相同的最大得分

如果有,则加上。

代码

class Solution {
public:
    int mod = 1000000007;
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int m = board.size();
        if(m == 0) {
            return {0,0};
        }
        int n = board[0].size();
        vector<vector<vector<int>>> dp(m,vector<vector<int>>(n,vector<int>(2)));
        for(int i = m-1;i >= 0;i--) {
            for(int j = n-1;j >= 0;j--) {
                //S位置的得分为0,路径数为1
                if (i == m-1 && j == n-1) {
                    dp[i][j] = {0,1};
                }
                else if (i == m-1) {//最后一行,只能从右边转移而来
                    if (board[i][j] != 'X' && (board[i][j+1] == 'S' || dp[i][j+1][0] != 0)) {
                        int result = (dp[i][j+1][0] + (board[i][j]-'0')) % mod;
                        dp[i][j] = {result,1};
                    }
                    else {
                        dp[i][j] = {0,0};
                    }
                }
                else if (j == n-1) {//最后一列,只能从下边转移而来
                    if (board[i][j] != 'X' && (board[i+1][j] == 'S' || dp[i+1][j][0] != 0)) {
                        int result = (dp[i+1][j][0] + (board[i][j]-'0')) % mod;
                        dp[i][j] = {result,1};
                    }
                    else {
                        dp[i][j] = {0,0};
                    }
                }
                else {
                    if (board[i][j] != 'X') {
                        //先算出最大得分
                        vector<vector<int>> tmp = {dp[i+1][j],dp[i+1][j+1],dp[i][j+1]};
                        int maxIndex = 0;
                        int max = dp[i+1][j][0];
                        for(int k = 1;k < 3;k++) {
                            if (tmp[k][0] > max) {
                                max = tmp[k][0];
                                maxIndex = k;
                            }
                        }
                        //然后找出相同的路径数
                        int path = tmp[maxIndex][1];
                        for(int k = 0;k < 3;k++) {
                            if (k != maxIndex && tmp[k][0] == max) {
                                path += tmp[k][1];
                                path %= mod;
                            }
                        }
                        //如果最大得分为0,并且路径数为0,则无路可通此处
                        if (max == 0 && path == 0) {
                            dp[i][j] = {0,0};
                        }
                        else {
                            if (board[i][j] == 'E') {
                                dp[i][j] = {max,path};
                            }
                            else {
                                int result = (max+(board[i][j]-'0'))%mod;
                                dp[i][j] = {result,path};
                            }
                        }
                    }
                    else {
                        dp[i][j] = {0,0};
                    }
                }
            }
        }
        return dp[0][0];
    }
};