最大得分的路径数目Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 解法

class Solution {

    // 网格型dp类问题。
    
    // 1. 寻找子问题。 假设我们现在在网格[i,j] 处。知道到这一点的最优策略，及到这点的最大和为Sum, 方案数为count. 
    // 我们可以从[i,j+1]， [i+1,j], [i+1,j+1] 三个坐标 移动到网格[i,j]。 假设我们分别也知道这三个位置的 最大和，方案数推导出[i,j]的值 。
    // 2. 我们可以定义dp[i][j][2]为在网格[i,j] 处 最大的Sum 和 count。 

    // 3.写出转移方程。
    // Sum (i,j) = dp[i][j][0] = max {Sum(i,j+1), Sum(i+1,j), Sum(i+1,j+1)} + board[i][j] -'0'，if board[i][j] != X

    // if board[i][j] == 'E', convert board[i][j] 到 0.
    // if board[i][j] == 'X' , Sum (i,j) = 0;

    // 维护一个变量 temp_max = max {Sum(i,j+1), Sum(i+1,j), Sum(i+1,j+1)}
    // Count(i,j) =  dp[i][j][1] = sum {count(m,n)} 如果上面的sum (m,n) 和 temp_max 保持一致，如果 if board[i][j] != 'X'
    // if board[i][j] == 'X' (自己是X)  如果count(i,j) == 0 （只有X能到达该位置), Sum (i,j) = 0;

    // 4. 初始状态：count 等于 1，sum 等于 0 即
    // dp[rows-1][cols-1][0] = 0; dp[rows-1][cols-1][1] = 1. 

    private static final int MOD = 1_000_000_007;
        


    public int[] pathsWithMaxScore(List<String> board) {
        int len = board.size();

        char[][] grid = new char[len][len];

        int row = 0;
        for(String str: board){
            char[] chs = str.toCharArray();
            for(int col = 0 ; col < len; col++){
                grid[row][col] = chs[col];
            }
            row += 1;
        }

        int[][][]  dp = new int[len][len][2];

        dp[len-1][len-1][0] = 0; 
        dp[len-1][len-1][1] = 1; 


        for(int r = len - 1 ; r >= 0; r--){
            for(int c = len -1; c >= 0; c--){

                if(r == len - 1 && c == len -1){
                    continue;
                }

                char curChar = grid[r][c];

                if (curChar == 'X'){
                    dp[r][c][0] = 0;
                    dp[r][c][1] = 0;
                    continue;
                }

                int max = Integer.MIN_VALUE;

                if ( r < len -1 ) max = Math.max(max,dp[r+1][c][0]);
                if ( c < len -1 )  max = Math.max(max,dp[r][c+1][0]);
                if ( r < len -1 && c < len -1 ) max = Math.max(max,dp[r+1][c+1][0]);

                dp[r][c][0] = (max + (curChar == 'E' ? 0 : curChar - '0') ) % MOD;

                int count = 0; 
                if ( r < len -1 && dp[r+1][c][0] == max) count = (count + dp[r+1][c][1]) % MOD;
                if ( c < len -1 && dp[r][c+1][0] == max) count = (count + dp[r][c+1][1]) % MOD;
                if ( r < len -1 && c < len -1 && dp[r+1][c+1][0] == max) count = (count + dp[r+1][c+1][1]) % MOD;

                dp[r][c][1] = count;
                if (count == 0) dp[r][c][0] = 0; 
            }
        }

        return dp[0][0];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

# 总结

分析出几种情况，然后分别对各个情况实现

#Java