Number of Paths with Max Score

Number of Paths with Max Score

What is this problem about?

The Number of Paths with Max Score problem gives you a square board where you start at the bottom-right corner and must reach the top-left. Cells contain digit scores, 'X' (blocked), 'S' (start), and 'E' (end). Find the maximum score achievable and the number of paths achieving that score. This hard coding problem uses 2D DP tracking both max score and path count.

Why is this asked in interviews?

Samsung and Amazon ask this because it requires tracking two values simultaneously in DP: the maximum achievable score and the count of paths achieving it. Any time you update to a new maximum, the count resets. Any time you match the current maximum, you add counts. The array, matrix, and dynamic programming interview pattern is exercised with dual-value state tracking.

Algorithmic pattern used

2D DP with (max_score, count) pairs. dp[i][j] = (max_score, count) for reaching cell (i,j) from the start. Movement goes up, left, or diagonally up-left. For each reachable cell, take the maximum score incoming path and sum their counts. If the cell is 'X', skip. Handle cells with digit values by adding the digit to incoming max scores.

Example explanation

Board:

"E23"
"2X2"
"12S"

From S=(2,2), move to adjacent accessible cells. Max path: S→(2,0)=1→(1,0)=2→(0,1)=2→E, score=1+2+2=5. Or other paths. Find max score and count of paths achieving it.

Common mistakes candidates make

• Not resetting count when a new maximum is found.
• Not summing counts from multiple predecessors when they all achieve the same max.
• Not handling 'X' cells (skip entirely, they have score -∞).
• Off-by-one in board indexing.

Interview preparation tip

Dual-value DP (max + count) appears whenever you need "maximum value AND the number of ways to achieve it." The rule: when updating dp[i][j], if new_score > current_max, replace; if new_score == current_max, add counts; if new_score < current_max, ignore. Practice this pattern on "number of shortest paths in a graph" — exact same dual-update logic.