#1301

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Paths with Max Score

Calculate the maximum score path and count all valid routes in a square board with obstacles using dynamic programming.

Problem Statement

You are given an n x n square board represented as an array of strings. Each cell contains a digit from '1' to '9', an obstacle 'X', a starting square 'S', or an ending square 'E'. You can move only up, left, or diagonally up-left from your current position and cannot pass through obstacles.

Return a list of two integers: the first is the maximum sum of numeric characters collected along any path from 'S' to 'E', and the second is the total number of distinct paths that achieve this sum, modulo 10^9 + 7. If no path exists, return [0,0].

Examples

Example 1

Input: board = ["E23","2X2","12S"]

Output: [7,1]

Example details omitted.

Example 2

Input: board = ["E12","1X1","21S"]

Output: [4,2]

Example details omitted.

Example 3

Input: board = ["E11","XXX","11S"]

Output: [0,0]

Example details omitted.

Constraints

2 <= board.length == board[i].length <= 100

Solution Approach

Define DP State and Base Cases

Use a 2D DP array where each cell stores a tuple of (max_sum, path_count). Initialize the starting cell 'S' with (0,1) and all obstacle cells with (0,0). This setup prepares the board for bottom-up state transitions.

Perform State Transitions

Iterate from bottom-right to top-left. For each non-obstacle cell, check the three allowed moves (up, left, up-left). Update max_sum as the cell value plus the maximum from reachable neighbors. Accumulate path_count only from neighbors that contribute to the current max_sum, ensuring correct counting.

Extract Result and Handle Edge Cases

After filling the DP table, the top-left cell 'E' contains the answer. If path_count is zero, return [0,0]. Apply modulo 10^9 + 7 when counting paths to handle large numbers and prevent overflow. Edge cases include fully blocked paths or boards with minimal size.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) since each cell is processed once and each has at most three neighbors. Space complexity is O(n^2) for the DP table, but can be reduced to O(n) by storing only the current and previous row.

What Interviewers Usually Probe

Can you define a DP state that tracks both sum and count together?
How do you handle obstacles in the dynamic programming transition?
What edge cases cause path count to be zero despite numeric values on the board?

Common Pitfalls or Variants

Common pitfalls

Counting paths from neighbors that do not contribute to max_sum, inflating path counts.
Failing to initialize the starting cell or obstacles correctly, causing DP propagation errors.
Ignoring the modulo requirement for path counts, leading to integer overflow.

Follow-up variants

Allow moves in all four directions, changing the state transition rules.
Compute minimum score paths instead of maximum, requiring adjustment in comparison logic.
Use larger boards with more obstacles, testing space optimization strategies.

FAQ

What is the main pattern used in Number of Paths with Max Score?

The problem follows a state transition dynamic programming pattern, tracking max sum and path counts simultaneously.

Can I move diagonally in this problem?

Yes, moves are allowed up, left, or diagonally up-left, but only if no obstacles block the cell.

What if there is no valid path from 'S' to 'E'?

You should return [0,0] to indicate both zero max sum and zero path count.

How do I handle large path counts?

Always apply modulo 10^9 + 7 when updating path counts to prevent overflow.

What is a common mistake in implementing this DP?

A frequent error is including neighbors that do not contribute to the current max sum, inflating the number of paths.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the maximum score from the starting point $(n - 1, n - 1)$ to $(i, j)$, and $g[i][j]$ to represent the number of ways to achieve the maximum score from the starting point $(n - 1, n - 1)$ to $(i, j)$. Initially, $f[n - 1][n - 1] = 0$ and $g[n - 1][n - 1] = 1$. The other positions of $f[i][j]$ are all $-1$, and $g[i][j]$ are all $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

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        def update(i, j, x, y):
            if x >= n or y >= n or f[x][y] == -1 or board[i][j] in "XS":
                return
            if f[x][y] > f[i][j]:
                f[i][j] = f[x][y]
                g[i][j] = g[x][y]
            elif f[x][y] == f[i][j]:
                g[i][j] += g[x][y]

        n = len(board)
        f = [[-1] * n for _ in range(n)]
        g = [[0] * n for _ in range(n)]
        f[-1][-1], g[-1][-1] = 0, 1
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                update(i, j, i + 1, j)
                update(i, j, i, j + 1)
                update(i, j, i + 1, j + 1)
                if f[i][j] != -1 and board[i][j].isdigit():
                    f[i][j] += int(board[i][j])
        mod = 10**9 + 7
        return [0, 0] if f[0][0] == -1 else [f[0][0], g[0][0] % mod]

Continue Practicing

#1289 minimum falling path sum ii #1277 count square submatrices with all ones #1349 maximum students taking exam