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 <= 100#1301 Number of Paths with Max Score is a grid-based dynamic programming problem where the goal is to move from the start cell to the end cell while maximizing the collected score and counting how many paths achieve that maximum. The board contains digits, obstacles (X), and special start/end cells.
A common approach is to use dynamic programming on the matrix, processing cells in reverse order (from bottom-right toward top-left). For each cell, maintain two values: the maximum score achievable from that position and the number of ways to obtain that score. Transitions consider three possible moves (down, right, and diagonal) while ignoring blocked cells.
When multiple directions yield the same maximum score, their path counts are combined using modulo arithmetic (typically 1e9+7). Careful handling of obstacles and edge boundaries is essential. This approach efficiently tracks both optimal score and path count across the grid.
The algorithm runs in linear time relative to the number of cells and uses a DP table to store intermediate results.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming on Grid | O(n × n) | O(n × n) |
| Optimized DP (rolling or in-place) | O(n × n) | O(n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming to find the path with the max score.
Use another dynamic programming array to count the number of paths with max score.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem requires not only finding the maximum score but also counting how many paths produce that score. Tracking both values in the DP state ensures we correctly accumulate paths when multiple directions yield the same optimal score.
Yes, variations of grid dynamic programming problems like this appear in FAANG and other top tech interviews. They test understanding of state transitions, path counting, and handling multiple optimal solutions in matrix-based problems.
The optimal approach uses dynamic programming on the grid. Each cell stores the maximum score achievable from that position and the number of ways to reach that score. By evaluating transitions from neighboring cells and combining counts when scores tie, we can compute the final answer efficiently.
A 2D dynamic programming table is typically used, where each entry stores a pair consisting of the best score and the number of ways to achieve it. This structure allows efficient updates when considering transitions from adjacent cells in the grid.