You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.
You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.
Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.
In case there is no path, return [0, 0].
Example 1:
Input: board = ["E23","2X2","12S"] Output: [7,1]
Example 2:
Input: board = ["E12","1X1","21S"] Output: [4,2]
Example 3:
Input: board = ["E11","XXX","11S"] Output: [0,0]
Constraints:
2 <= board.length == board[i].length <= 100Problem Overview: You are given an n x n board containing digits, obstacles (X), a start cell S, and an end cell E. Starting from S (bottom‑right), you can move up, left, or diagonally up‑left until reaching E. Each path collects numeric values from cells, and the goal is to compute the maximum possible score and the number of distinct paths that achieve that score.
Approach 1: Dynamic Programming (State Tracking) (Time: O(n²), Space: O(n²))
This solution uses a DP table where each cell stores two values: the maximum score achievable when reaching that cell and the number of ways to achieve that score. Starting from S, you iterate through the grid in reverse directions that match the allowed moves (up, left, diagonal). For every valid cell, check the three predecessor states and choose the one producing the highest score. If multiple predecessors produce the same score, sum their path counts (mod 1e9+7). This works well because each cell’s result depends only on previously computed states, a classic pattern in dynamic programming.
Approach 2: Dynamic Programming from Bottom‑Right to Top‑Left (Time: O(n²), Space: O(n²))
This is the most common implementation used in interviews. Instead of expanding from the start, the algorithm fills the DP table while scanning the grid from bottom‑right to top‑left. At each cell, examine the three reachable neighbors (down, right, and down‑right) that represent valid forward moves. Compute the best score among them, then update the current cell’s score and path count accordingly. Obstacles (X) immediately invalidate states. Because each cell is processed exactly once, the algorithm runs in O(n²) time and efficiently handles grids up to typical constraints. The grid traversal pattern is common in matrix DP problems.
Approach 3: Breadth‑First Search with Priority Queue (Time: O(n² log n), Space: O(n²))
This alternative models the board as a graph. Each cell is a node and edges represent valid moves. A max‑priority queue always expands the state with the highest accumulated score first, similar to a modified Dijkstra traversal. For each expansion, update neighbor states if a higher score is found or if an equal score adds additional paths. While conceptually intuitive for graph thinking, the priority queue introduces a log factor and makes it slower than pure DP. This approach highlights how grid traversal problems can also be framed as graph searches over an array structure.
Recommended for interviews: The bottom‑right to top‑left dynamic programming solution is what most interviewers expect. It shows you can translate grid movement constraints into DP state transitions and track both score and path counts simultaneously. A brute‑force search would explore exponentially many paths, so demonstrating the DP optimization proves strong algorithmic reasoning.
In this approach, the idea is to use dynamic programming to keep track of the maximum score and the number of ways to achieve it, starting from the end point 'S' and working backwards to the start point 'E'. We will initialize a dp array where each cell will store two values: the maximum score to reach this cell and the number of ways to achieve that score. We iterate over each cell and update its value based on possible movements from the neighboring cells (up, left, and up-left) that are not blocked by an obstacle 'X'.
The solution uses a double array `dp` where `dp[i][j]` contains a tuple `(max_sum, path_count)` representing the maximum sum that can be collected to reach the cell `(i, j)` and the number of ways to reach that maximum sum. We start from 'S', marked initially with `(0, 1)`, meaning we start with sum 0 and 1 way. While iterating, we update cells with possible movements from adjacent cells. The time complexity is O(n^2), where n is the size of the board, and the space complexity is also O(n^2) due to the auxiliary array `dp`.
Time Complexity: O(n^2) where n is the dimension of the square board.
Space Complexity: O(n^2) for the dp array.
Strategy: In this approach, we'll use dynamic programming to track the maximum path sum and the number of possible such paths from the start square 'S' to the end square 'E'. We'll initialize the bottom-right corner and populate upwards and leftwards.
We use a 2D array for max scores and paths. For each cell not blocked by 'X', the value of max score and path count is determined by considering up, left, and diagonal moves, ensuring to add the numeric value of the current cell to the path sum.
This C solution initializes a DP table where each cell represents the maximum score obtainable ending at that cell and how many ways it can be achieved. The program starts from 'S' and fills backwards to 'E', considering potential upward, leftward, and diagonal moves.
Time Complexity: O(n^2), where n is the length of the board's edge.
Space Complexity: O(n^2), for the DP table.
Strategy: In this BFS approach, prioritize exploring paths with higher sums by deploying a max-heap structure, ensuring the most beneficial paths are expanded first. We'll backtrack from 'S' to 'E' while updating our path scores dynamically based on BFS execution order.
The C solution utilizes a BFS algorithm with a priority queue to determine all maximum possible paths. This ensures the highest sum paths are considered first, dynamically updating possible path scores using an adjacency-list-like mechanism, yet optimized using max-heaps for faster calculations.
Time Complexity: O(n^2 log n), due to the priority queue.
Space Complexity: O(n^2).
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.
For the current position (i, j), it can be transferred from three positions: (i + 1, j), (i, j + 1), and (i + 1, j + 1). Therefore, we can enumerate these three positions to update the values of f[i][j] and g[i][j]. If the current position (i, j) has an obstacle, or the current position is the starting point, or other positions are out of bounds, no update is performed. Otherwise, if another position (x, y) satisfies f[x][y] \gt f[i][j], then we update f[i][j] = f[x][y] and g[i][j] = g[x][y]. If f[x][y] = f[i][j], then we update g[i][j] = g[i][j] + g[x][y]. Finally, if the current position (i, j) is reachable and is a number, we update f[i][j] = f[i][j] + board[i][j].
Finally, if f[0][0] \lt 0, it means there is no path to reach the endpoint, return [0, 0]. Otherwise, return [f[0][0], g[0][0]]. Note that the result needs to be taken modulo 10^9 + 7.
Time complexity O(n^2), space complexity O(n^2). Where n is the side length of the array.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) where n is the dimension of the square board. |
| Dynamic Programming from Bottom-Right to Top-Left | Time Complexity: O(n^2), where n is the length of the board's edge. |
| Breadth-First Search with Priority Queue | Time Complexity: O(n^2 log n), due to the priority queue. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Tracking) | O(n²) | O(n²) | General solution when computing best score and number of ways simultaneously |
| DP Bottom‑Right to Top‑Left | O(n²) | O(n²) | Most common interview implementation for grid DP problems |
| BFS with Priority Queue | O(n² log n) | O(n²) | Useful when modeling the grid as a graph with weighted paths |
花花酱 LeetCode 1301. Number of Paths with Max Score - 刷题找工作 EP289 • Hua Hua • 1,339 views views
Watch 9 more video solutions →Practice Number of Paths with Max Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor