DSA Round: Maximum Score Grid Path

You are given a rectangular grid board of size N x M, where each cell contains an integer. A player starts from cell (0, p) in the top row. The objective is to reach the bottom row of the grid while maximizing the total score collected.
From a cell (i, j), the player may move to:
(i + 1, j - 1), diagonally left-down
(i + 1, j), straight down
(i + 1, j + 1), diagonally right-down
(i + 2, j), using a special jump move
The player must always remain inside the grid boundaries. The special jump move (i + 2, j) may be used at most k times during the traversal.
The total score is equal to the sum of all visited cell values, including the starting cell and the final cell.
Complete the function maximizeGridPathScore. It should return a String[] with exactly three values:
result[0]: the maximum achievable score from the starting cell to any cell in the last row.
result[1]: one path that produces the maximum score, formatted as coordinates joined by ->, for example (0,1)->(1,1).
result[2]: the number of distinct maximum-score paths modulo 10^9 + 7.
If multiple maximum-score paths exist, return the lexicographically smallest coordinate sequence as the path in result[1]. Compare two paths by their coordinate pairs from left to right; the smaller row wins first, then the smaller column.
What the interview report shared
The source described an OpenAI onsite DSA round problem about maximizing score while moving through a rectangular integer grid. It listed the four allowed moves, including a limited special jump, and asked for the maximum score, one maximum-score path, and the count of maximum-score paths modulo 10^9 + 7.
How FastPrep adapted it
FastPrep kept the source task and example board, and added a deterministic return format so the problem can be practiced and checked here. The source asked for one valid maximum-score path but did not specify how to choose among ties, so FastPrep uses the lexicographically smallest maximum-score coordinate sequence for that returned path.

Function
maximizeGridPathScore(board: int[][], p: int, k: int) → String[]

Examples
Example 1
board = [[1,2,3,4],[5,6,1,2],[7,8,9,1],[3,2,5,6]]
p = 1
k = 1
return = ["23","(0,1)->(1,1)->(2,2)->(3,3)","1"]
One maximum-score path is (0,1)->(1,1)->(2,2)->(3,3).
Visited values: 2 + 6 + 9 + 6 = 23.
The alternate valid jump path shown in the source, (0,1)->(2,1)->(3,2), scores 2 + 8 + 5 = 15, so it is not a maximum-score path.
There is exactly one maximum-score path for this example.
The source image provided valid path examples but did not state the final output values; these values follow directly from the source board and movement rules.

Constraints
board is rectangular and contains integers.
p is a valid column index in the top row.
The player may use the special jump at most k times.
Return the maximum-path count modulo 10^9 + 7.

The trick is that state is (row, col, jumpsUsed). Every move goes strictly down, so the graph is a DAG and you can do DP row by row. BFS-style layering works, but a forward or backward DP is cleaner. Keep three values per state: best score, path count mod 1e9+7, and a way to rebuild the smallest path. Pitfall one: dropping the k dimension, so jumps get overused. Pitfall two: counting paths with a mod on the score, or adding counts when scores are strictly less. Only add counts on ties. Pitfall three: lexicographic ties. Compute DP from the bottom up (best from this state to the end), then walk forward from (0,p) and at each step pick the smallest (row, col) among moves that preserve the optimum. Final answer takes the max across last-row cells and all jump counts up to k, summing counts of ties. StealthCoder is your hedge if the reconstruction logic slips live.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.