Skip to content

1301. Number of Paths with Max Score 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  vector<int> pathsWithMaxScore(vector<string>& board) {
    constexpr int kMod = 1'000'000'007;
    const int n = board.size();
    const vector<pair<int, int>> dirs{{0, 1}, {1, 0}, {1, 1}};
    // dp[i][j] := the maximum sum from (n - 1, n - 1) to (i, j)
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
    // count[i][j] := the number of paths to get dp[i][j] from (n - 1, n - 1) to
    // (i, j)
    vector<vector<int>> count(n + 1, vector<int>(n + 1));

    dp[0][0] = 0;
    dp[n - 1][n - 1] = 0;
    count[n - 1][n - 1] = 1;

    for (int i = n - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j) {
        if (board[i][j] == 'S' || board[i][j] == 'X')
          continue;
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (dp[i][j] < dp[x][y]) {
            dp[i][j] = dp[x][y];
            count[i][j] = count[x][y];
          } else if (dp[i][j] == dp[x][y]) {
            count[i][j] += count[x][y];
            count[i][j] %= kMod;
          }
        }
        // If there's path(s) from 'S' to (i, j) and the cell is not 'E'.
        if (dp[i][j] != -1 && board[i][j] != 'E') {
          dp[i][j] += board[i][j] - '0';
          dp[i][j] %= kMod;
        }
      }

    return {dp[0][0], count[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
class Solution {
  public int[] pathsWithMaxScore(List<String> board) {
    final int kMod = 1_000_000_007;
    final int n = board.size();
    final int[][] dirs = {{0, 1}, {1, 0}, {1, 1}};
    // dp[i][j] := the maximum sum from (n - 1, n - 1) to (i, j)
    int[][] dp = new int[n + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));
    // count[i][j] := the number of paths to get dp[i][j] from (n - 1, n - 1) to (i, j)
    int[][] count = new int[n + 1][n + 1];

    dp[0][0] = 0;
    dp[n - 1][n - 1] = 0;
    count[n - 1][n - 1] = 1;

    for (int i = n - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j) {
        if (board.get(i).charAt(j) == 'S' || board.get(i).charAt(j) == 'X')
          continue;
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (dp[i][j] < dp[x][y]) {
            dp[i][j] = dp[x][y];
            count[i][j] = count[x][y];
          } else if (dp[i][j] == dp[x][y]) {
            count[i][j] += count[x][y];
            count[i][j] %= kMod;
          }
        }
        // If there's path(s) from 'S' to (i, j) and the cell is not 'E'.
        if (dp[i][j] != -1 && board.get(i).charAt(j) != 'E') {
          dp[i][j] += board.get(i).charAt(j) - '0';
          dp[i][j] %= kMod;
        }
      }

    return new int[] {dp[0][0], count[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
class Solution:
  def pathsWithMaxScore(self, board: List[str]) -> List[int]:
    kMod = 1_000_000_007
    n = len(board)
    dirs = ((0, 1), (1, 0), (1, 1))
    # dp[i][j] := the maximum sum from (n - 1, n - 1) to (i, j)
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    # count[i][j] := the number of paths to get dp[i][j] from (n - 1, n - 1) to
    # (i, j)
    count = [[0] * (n + 1) for _ in range(n + 1)]

    dp[0][0] = 0
    dp[n - 1][n - 1] = 0
    count[n - 1][n - 1] = 1

    for i in reversed(range(n)):
      for j in reversed(range(n)):
        if board[i][j] == 'S' or board[i][j] == 'X':
          continue
        for dx, dy in dirs:
          x = i + dx
          y = j + dy
          if dp[i][j] < dp[x][y]:
            dp[i][j] = dp[x][y]
            count[i][j] = count[x][y]
          elif dp[i][j] == dp[x][y]:
            count[i][j] += count[x][y]
            count[i][j] %= kMod

        # If there's path(s) from 'S' to (i, j) and the cell is not 'E'.
        if dp[i][j] != -1 and board[i][j] != 'E':
          dp[i][j] += int(board[i][j])
          dp[i][j] %= kMod

    return [dp[0][0], count[0][0]]