1301. Number of Paths with Max Score
Difficulty: Hard | Date: 2026-07-05
Patterns: Dynamic Programming | DFS Data Structures: Matrix
Problem
Given an n×m board of characters ('E' top-left, 'S' bottom-right, 'X' for walls, digits for scores), find the maximum score collectible on any path from 'E' to 'S' moving only right, down, or diagonally down-right. Return [max_score, num_paths] where num_paths is the count of paths achieving that score, modulo 10^9+7. Return [0, 0] if no path exists.
My Approach
Recognized this as DP immediately. The tricky part is the second return value - not just finding the max score but counting all paths that achieve it. Started with top-down memoized DFS from 'E' toward 'S', where each cell returns (max_score, num_paths). The key challenge was correctly combining results from three neighbors without letting dead-end paths (count=0) corrupt the best_score calculation.
Key Insight
Each cell stores (max_score, num_paths) as a pair. When combining from multiple neighbors, only consider neighbors where count > 0 - a neighbor with count=0 is a dead end and its score is meaningless. Among valid neighbors, take the max score and sum the counts of all that tie for that max. This sentinel pattern (count=0 = unreachable) propagates correctly through the whole grid.
Solution
Top-Down (Memoized DFS)
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
MOD = 10**9 + 7
ROWS, COLS = len(board), len(board[0])
def convert_cell_val(i, j):
if board[i][j] in ('E', 'S'):
return 0
return int(board[i][j])
def dfs(i, j):
if (i, j) == (ROWS - 1, COLS - 1):
return [0, 1]
if not (0 <= i < ROWS and 0 <= j < COLS):
return [0, 0]
if board[i][j] == 'X':
return [0, 0]
if (i, j) in memo:
return memo[(i, j)]
down = dfs(i + 1, j)
right = dfs(i, j + 1)
down_right = dfs(i + 1, j + 1)
res = [down, right, down_right]
best_score = max(score if num_path > 0 else 0 for score, num_path in res)
num_paths = 0
for score, num_path in res:
if score == best_score and num_path > 0:
num_paths += num_path
cell_val = convert_cell_val(i, j)
memo[(i, j)] = [best_score + cell_val, num_paths % MOD]
return memo[(i, j)]
memo = {}
result = dfs(0, 0)
return result if result[1] > 0 else [0, 0]Bottom-Up (Iterative DP)
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
MOD = 10**9 + 7
ROWS, COLS = len(board), len(board[0])
# Extra row/col of [0,0] handles out-of-bounds naturally
dp = [[[0, 0] for _ in range(COLS + 1)] for _ in range(ROWS + 1)]
dp[ROWS - 1][COLS - 1] = [0, 1]
for i in range(ROWS - 1, -1, -1):
for j in range(COLS - 1, -1, -1):
if (i, j) == (ROWS - 1, COLS - 1):
continue
if board[i][j] == 'X':
continue
neighbors = [dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]]
valid = [(s, c) for s, c in neighbors if c > 0]
if not valid:
continue
best_score = max(s for s, _ in valid)
num_paths = sum(c for s, c in valid if s == best_score)
cell_val = 0 if board[i][j] in ('E', 'S') else int(board[i][j])
dp[i][j] = [best_score + cell_val, num_paths % MOD]
return dp[0][0] if dp[0][0][1] > 0 else [0, 0]Complexity
- Time: O(n*m) - each cell visited once with memoization
- Space: O(n*m) - memo table / dp table; bottom-up wins nothing on space here but is iterative
Prerequisites
Review Log
- 2026-07-25 [Good] - fuzzy: sentinel pattern (num_paths==0 = dead end) and base case at ‘S’ must return [0,1] not [0,0]; clicked: DP structure, combining neighbors by max score + summing tied counts