LeetCode 1301 - Number of Paths with Max Score

In this problem, we are given an n x n board where each cell contains one of four possible values: - 'E', the ending position located at the top-left corner - 'S', the starting position located at the bottom-right corner - A digit character '1' through '9', representing points…

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 1301

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

In this problem, we are given an n x n board where each cell contains one of four possible values:

  • 'E', the ending position located at the top-left corner
  • 'S', the starting position located at the bottom-right corner
  • A digit character '1' through '9', representing points that can be collected
  • 'X', representing an obstacle that cannot be traversed

The goal is to move from 'S' to 'E' while maximizing the total score collected along the path. The score is the sum of all numeric cells visited. The 'S' and 'E' cells themselves do not contribute to the score.

The movement rules are restrictive. From any position, we may only move:

  • Up
  • Left
  • Up-left diagonally

Because we start at the bottom-right and move toward the top-left, these are the only legal directions.

The output requires two values:

  1. The maximum score achievable among all valid paths
  2. The number of distinct paths that achieve this maximum score

The number of paths must be returned modulo:

10^9 + 7

If no valid path exists from 'S' to 'E', the answer should be:

[0, 0]

The board size can be as large as 100 x 100. This constraint is extremely important because it tells us that exponential path exploration is infeasible. A brute-force depth-first search would potentially explore an enormous number of paths. Since the state space is relatively small and movements are directional, this strongly suggests a dynamic programming solution.

Several edge cases are important:

  • The path may be completely blocked by obstacles
  • Multiple paths may achieve the same maximum score
  • The optimal path may require diagonal movement
  • The board may contain many obstacles that disconnect regions
  • The maximum-score path is not necessarily the shortest path
  • Cells 'S' and 'E' should not contribute numeric values

Approaches

Brute Force Approach

A straightforward solution is to recursively explore every possible path from 'S' to 'E'.

At each cell, we attempt the three allowed moves:

  • Up
  • Left
  • Diagonal up-left

For every valid path that eventually reaches 'E', we compute the score collected along that path. After exploring all possible paths, we determine:

  • The maximum score among all paths
  • How many paths achieve that maximum

This approach is correct because it explicitly enumerates every legal path and evaluates them all.

However, it is far too slow. Even without obstacles, each position can branch into as many as three recursive calls. The number of paths grows exponentially with board size. For a 100 x 100 board, exhaustive exploration becomes completely impractical.

The core inefficiency is repeated computation. Many different recursive paths revisit the same subproblems, meaning we recompute the best result for the same cell many times.

Optimal Dynamic Programming Approach

The key insight is that the best result for a cell depends only on the best results of the cells that can reach it.

Since movement directions are fixed, the board forms a directed acyclic graph. This makes dynamic programming a natural fit.

For every cell (r, c), we want to compute two pieces of information:

  • The maximum score achievable upon reaching that cell
  • The number of ways to achieve that maximum score

We can transition from:

  • (r + 1, c) , below
  • (r, c + 1) , right
  • (r + 1, c + 1) , diagonal down-right

This is easier because we process from bottom-right toward top-left.

For each candidate predecessor:

  • If it provides a larger score, we replace the current best
  • If it provides the same score, we add its path count

This avoids recomputation entirely and processes each cell once.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^(n²)) O(n²) recursion stack Explores every possible path
Optimal Dynamic Programming O(n²) O(n²) Computes best score and path counts once per cell

Algorithm Walkthrough

  1. Create two DP tables of size n x n.

The first table, max_score, stores the maximum score obtainable when reaching each cell.

The second table, path_count, stores how many paths achieve that maximum score. 2. Initialize all cells as unreachable.

We can use -1 in max_score to represent an unreachable state. 3. Set the starting position.

Since we start at 'S', located at (n-1, n-1):

  • max_score[n-1][n-1] = 0
  • path_count[n-1][n-1] = 1

The score starts at zero because 'S' contributes no points. 4. Iterate through the board from bottom-right toward top-left.

This traversal order guarantees that when processing a cell, all cells that can move into it have already been computed. 5. Skip invalid cells.

If a cell contains 'X', it is blocked and cannot be entered. 6. For each cell, examine the three possible predecessor positions.

These are:

  • Down (r + 1, c)
  • Right (r, c + 1)
  • Down-right diagonal (r + 1, c + 1)

These correspond to valid forward moves from 'S'. 7. Determine the best predecessor score.

Among all reachable predecessors, find the maximum score. 8. Compute the number of optimal paths.

For every predecessor achieving the best score:

  • Add its path count to the current cell
  • Apply modulo 10^9 + 7
  1. Add the current cell's numeric value.

If the current cell contains a digit, add it to the best predecessor score.

Do not add values for 'S' or 'E'. 10. Continue until the entire board has been processed. 11. Return the result for the top-left cell.

If the top-left cell is unreachable, return [0, 0].

Why it works

The dynamic programming invariant is:

max_score[r][c] always stores the maximum achievable score when reaching (r, c), and path_count[r][c] stores the number of paths achieving exactly that score.

Every valid path to a cell must come from one of the three allowed predecessor cells. Since we process cells in reverse topological order, all predecessor states are already finalized before computing the current cell. Therefore, selecting the maximum predecessor score and combining counts for ties guarantees correctness.

Python Solution

from typing import List

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        MOD = 10**9 + 7
        n = len(board)

        max_score = [[-1] * n for _ in range(n)]
        path_count = [[0] * n for _ in range(n)]

        max_score[n - 1][n - 1] = 0
        path_count[n - 1][n - 1] = 1

        for row in range(n - 1, -1, -1):
            for col in range(n - 1, -1, -1):

                if board[row][col] == 'X':
                    continue

                if row == n - 1 and col == n - 1:
                    continue

                best_score = -1
                ways = 0

                directions = [
                    (row + 1, col),
                    (row, col + 1),
                    (row + 1, col + 1)
                ]

                for nr, nc in directions:
                    if nr >= n or nc >= n:
                        continue

                    if max_score[nr][nc] == -1:
                        continue

                    candidate_score = max_score[nr][nc]

                    if candidate_score > best_score:
                        best_score = candidate_score
                        ways = path_count[nr][nc]

                    elif candidate_score == best_score:
                        ways = (ways + path_count[nr][nc]) % MOD

                if best_score == -1:
                    continue

                cell = board[row][col]

                if cell.isdigit():
                    best_score += int(cell)

                max_score[row][col] = best_score
                path_count[row][col] = ways % MOD

        if max_score[0][0] == -1:
            return [0, 0]

        return [max_score[0][0], path_count[0][0]]

The implementation begins by creating two dynamic programming tables.

max_score[row][col] stores the best possible score obtainable upon reaching that cell. A value of -1 indicates the cell is unreachable.

path_count[row][col] stores how many optimal paths achieve that best score.

The starting position 'S' is initialized with score 0 and path count 1.

The board is processed from bottom-right toward top-left. This ordering is critical because each cell depends only on states below, to the right, or diagonally down-right.

For each cell, the algorithm checks all valid predecessor states. If a predecessor produces a larger score, it becomes the new best option. If another predecessor produces the same score, its path count is added.

After determining the best predecessor score, the current cell's digit value is added if applicable.

Finally, the top-left cell is examined. If unreachable, the function returns [0, 0].

Go Solution

func pathsWithMaxScore(board []string) []int {
    const MOD int = 1e9 + 7

    n := len(board)

    maxScore := make([][]int, n)
    pathCount := make([][]int, n)

    for i := 0; i < n; i++ {
        maxScore[i] = make([]int, n)
        pathCount[i] = make([]int, n)

        for j := 0; j < n; j++ {
            maxScore[i][j] = -1
        }
    }

    maxScore[n-1][n-1] = 0
    pathCount[n-1][n-1] = 1

    for row := n - 1; row >= 0; row-- {
        for col := n - 1; col >= 0; col-- {

            if board[row][col] == 'X' {
                continue
            }

            if row == n-1 && col == n-1 {
                continue
            }

            bestScore := -1
            ways := 0

            directions := [][]int{
                {row + 1, col},
                {row, col + 1},
                {row + 1, col + 1},
            }

            for _, dir := range directions {
                nr := dir[0]
                nc := dir[1]

                if nr >= n || nc >= n {
                    continue
                }

                if maxScore[nr][nc] == -1 {
                    continue
                }

                candidate := maxScore[nr][nc]

                if candidate > bestScore {
                    bestScore = candidate
                    ways = pathCount[nr][nc]
                } else if candidate == bestScore {
                    ways = (ways + pathCount[nr][nc]) % MOD
                }
            }

            if bestScore == -1 {
                continue
            }

            cell := board[row][col]

            if cell >= '0' && cell <= '9' {
                bestScore += int(cell - '0')
            }

            maxScore[row][col] = bestScore
            pathCount[row][col] = ways % MOD
        }
    }

    if maxScore[0][0] == -1 {
        return []int{0, 0}
    }

    return []int{maxScore[0][0], pathCount[0][0]}
}

The Go implementation mirrors the Python logic closely. Since Go does not provide automatic multidimensional array initialization with default values other than zero, the maxScore matrix must be explicitly initialized to -1.

Character handling is also slightly different. Instead of isdigit(), Go checks whether the byte value lies between '0' and '9'.

All arithmetic fits safely within Go's int type because the maximum possible score is relatively small, at most 9 * 100 * 100.

Worked Examples

Example 1

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

We initialize:

Cell max_score path_count
S(2,2) 0 1

Now process backward.

Processing Cell (2,1)

Cell value = '2'

Possible predecessors:

  • (2,2) → score 0

New score:

0 + 2 = 2
Cell max_score path_count
(2,1) 2 1

Processing Cell (2,0)

Cell value = '1'

Predecessor:

  • (2,1) → score 2

New score:

2 + 1 = 3
Cell max_score path_count
(2,0) 3 1

Processing Cell (1,2)

Cell value = '2'

Predecessor:

  • (2,2) → score 0

New score:

0 + 2 = 2
Cell max_score path_count
(1,2) 2 1

Processing Cell (1,1)

Obstacle 'X'

Skip.

Processing Cell (1,0)

Cell value = '2'

Predecessors:

  • (2,0) → 3
  • (2,1) → 2

Best predecessor score = 3

New score:

3 + 2 = 5
Cell max_score path_count
(1,0) 5 1

Processing Cell (0,2)

Cell value = '3'

Predecessor:

  • (1,2) → 2

New score:

2 + 3 = 5
Cell max_score path_count
(0,2) 5 1

Processing Cell (0,1)

Cell value = '2'

Predecessors:

  • (0,2) → 5
  • (1,2) → 2

Best predecessor = 5

New score:

5 + 2 = 7
Cell max_score path_count
(0,1) 7 1

Processing Cell (0,0)

Cell = 'E'

Predecessors:

  • (0,1) → 7
  • (1,0) → 5

Best predecessor = 7

Final:

[7, 1]

Example 2

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

Two different optimal paths produce score 4.

The DP eventually computes:

Cell max_score path_count
(0,0) 4 2

Final answer:

[4, 2]

Example 3

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

The middle row blocks all movement.

No reachable state ever reaches (0,0).

Thus:

Cell max_score path_count
(0,0) -1 0

Final answer:

[0, 0]

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every cell is processed once, with constant work per cell
Space O(n²) Two DP tables of size n x n are stored

The algorithm visits each cell exactly once. For every cell, only three neighboring states are examined, so the work per cell is constant.

The space usage comes from storing the max_score and path_count matrices.

Test Cases

from typing import List

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        MOD = 10**9 + 7
        n = len(board)

        max_score = [[-1] * n for _ in range(n)]
        path_count = [[0] * n for _ in range(n)]

        max_score[n - 1][n - 1] = 0
        path_count[n - 1][n - 1] = 1

        for row in range(n - 1, -1, -1):
            for col in range(n - 1, -1, -1):

                if board[row][col] == 'X':
                    continue

                if row == n - 1 and col == n - 1:
                    continue

                best_score = -1
                ways = 0

                for nr, nc in [
                    (row + 1, col),
                    (row, col + 1),
                    (row + 1, col + 1)
                ]:
                    if nr >= n or nc >= n:
                        continue

                    if max_score[nr][nc] == -1:
                        continue

                    candidate = max_score[nr][nc]

                    if candidate > best_score:
                        best_score = candidate
                        ways = path_count[nr][nc]
                    elif candidate == best_score:
                        ways = (ways + path_count[nr][nc]) % MOD

                if best_score == -1:
                    continue

                if board[row][col].isdigit():
                    best_score += int(board[row][col])

                max_score[row][col] = best_score
                path_count[row][col] = ways

        if max_score[0][0] == -1:
            return [0, 0]

        return [max_score[0][0], path_count[0][0]]

solver = Solution()

assert solver.pathsWithMaxScore(["E23","2X2","12S"]) == [7,1]  # basic single optimal path

assert solver.pathsWithMaxScore(["E12","1X1","21S"]) == [4,2]  # multiple optimal paths

assert solver.pathsWithMaxScore(["E11","XXX","11S"]) == [0,0]  # completely blocked

assert solver.pathsWithMaxScore(["ES","11"]) == [1,1]  # smallest valid board

assert solver.pathsWithMaxScore(["E1","1S"]) == [1,2]  # two optimal routes

assert solver.pathsWithMaxScore(["E2X","121","11S"]) == [4,2]  # obstacle with multiple routes

assert solver.pathsWithMaxScore(["E99","999","99S"]) == [27,6]  # many high-value paths

assert solver.pathsWithMaxScore(["EX","XS"]) == [0,0]  # no path exists

assert solver.pathsWithMaxScore(["E12","XXX","21S"]) == [0,0]  # entire blocking row
Test Why
["E23","2X2","12S"] Validates standard single optimal path
["E12","1X1","21S"] Verifies counting multiple optimal paths
["E11","XXX","11S"] Ensures blocked boards return [0,0]
["ES","11"] Tests smallest board size
["E1","1S"] Verifies tie counting
["E2X","121","11S"] Tests obstacle navigation
["E99","999","99S"] Stress test with many high-value routes
["EX","XS"] Ensures impossible path detection
["E12","XXX","21S"] Tests full-row obstruction

Edge Cases

One important edge case occurs when no valid path exists between 'S' and 'E'. A naive implementation might accidentally return a score of zero with one path because the destination cell exists. However, unreachable states must be distinguished explicitly. This implementation uses -1 in max_score to represent unreachable cells, ensuring blocked configurations correctly return [0,0].

Another subtle edge case involves multiple optimal paths. Some implementations only track the best score and overwrite counts whenever a matching score appears. This loses information about equally optimal paths. The solution carefully accumulates counts whenever two predecessors produce the same maximum score.

Diagonal movement is another common source of bugs. Since the problem allows up-left diagonal movement, paths may exist even when straight directions are blocked. An implementation that only considers up and left moves would fail valid test cases. This solution explicitly checks all three predecessor directions for every cell.

A final edge case involves handling 'E' and 'S' correctly. These cells are not numeric and should not contribute to the score. Accidentally converting them to integers or treating them as zero-valued numeric cells can create incorrect totals. The implementation only adds values when cell.isdigit() is true.