# 1301. Number of Paths with Max Score
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/number-of-paths-with-max-score/
## 思路
此题仍然是经典的走迷宫的DP套路。只不过嵌套了两个DP小问题。第一个问题比较简单，设计状态变量```dp[i][j]```表示从右下角走到```(i,j)```位置的最大权重路径的权值和。大致的状态转移方程是

dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) + board[i][j]-'0'

当然coding的过程中要查验这三个前驱状态是否都存在，也就是处理好边界的情况。

第二个问题和第一个问题息息相关。我们知道```dp[i][j]```代表了从右下角走到```(i,j)```位置的最大权重路径，其本质是在三个前驱状态```dp[i+1]```,```dp[i][j+1]```,```dp[i+1][j+1]```中取最大的那一个。假设这三个前驱状态中```dp[i+1][j]```最大，说明```(i,j)```要取得最大权值路径，必须要先使得```(i+1,j)```取得最大权值路径。因此，从右下角到```(i+1,j)```的最大权重路径的条数```paths[i+1][j]```，就对应了有相同多数目的从右下角到```(i,j)```的最大权重路径，也就是```paths[i][j]```。

特别的，如果三个前驱状态中有若干个并列最大的，那么```paths[i][j]```就是这些前驱状态```paths[i+1]```,```paths[i][j+1]```,```paths[i+1][j+1]```的加和。
## Code

class Solution {
    public int[] pathsWithMaxScore(List<String> board) {
        int m = board.size(), n = board.get(0).length();
        int[][] scores = new int[m][n];
        for(int i=0; i<m; i++){
            Arrays.fill(scores[i],-1);
        }
        int[][] pathNum = new int[m][n];
        int mod = 1000000007;
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                if(board.get(i).charAt(j)=='X') continue;
                if(i==m-1 && j==n-1){
                    scores[i][j] = 0;
                    pathNum[i][j] = 1;
                    continue;
                }
                
                int right=-1, down=-1, dig=-1;
                if(j<n-1) right = scores[i][j+1];
                if(i<m-1) down = scores[i+1][j];
                if(j<n-1 && i<m-1) dig = scores[i+1][j+1];
                scores[i][j] = Math.max(right, Math.max(down, dig));
                if(scores[i][j] == -1) continue;
                
                if(j<n-1 && scores[i][j]==scores[i][j+1]) pathNum[i][j] = (pathNum[i][j]+pathNum[i][j+1])%mod;
                if(i<m-1 && scores[i][j]==scores[i+1][j]) pathNum[i][j] = (pathNum[i][j]+pathNum[i+1][j])%mod;
                if(j<n-1 && i<m-1 && scores[i][j]==scores[i+1][j+1]) pathNum[i][j] = (pathNum[i][j]+pathNum[i+1][j+1])%mod;
                if(i!=0 || j!=0) scores[i][j] += board.get(i).charAt(j)-'0';
            }
        }
        return scores[0][0]==-1?new int[2]:new int[]{scores[0][0], pathNum[0][0]};
    }
}