3742. Maximum Path Score in a Grid

MediumArrayDynamic ProgrammingMatrix

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an m x n grid where each cell contains one of the values 0, 1, or 2. You are also given an integer k.

You start from the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1) by moving only right or down.

Each cell contributes a specific score and incurs an associated cost, based on its value:

0: adds 0 to your score and costs 0.
1: adds 1 to your score and costs 1.
2: adds 2 to your score and costs 1.

In other words, every cell with a non-zero value (1 or 2) costs exactly 1, but a cell with value 2 gives you a higher score (2) than a cell with value 1 (1). Cells with value 0 are free and contribute nothing to either the score or the cost.

Your task is to find a path from (0, 0) to (m - 1, n - 1) such that the total score along the path is maximized, while the total cost along the path does not exceed k. The score and cost of a path are the sums of the scores and costs of all cells visited along that path.

Return the maximum score achievable without exceeding a total cost of k. If no valid path exists, return -1.

Note: If you reach the last cell but the total cost exceeds k, the path is considered invalid.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Right/down-only movement plus a cost budget constraint creates a 3D DP maximizing score under a cost limit.

Open in Flowchart

Intuition

The key observation is that at every step we can only move right or down. This means that to arrive at a cell (i, j), we must have come from either the cell directly above it (i-1, j) or the cell directly to its left (i, j-1). This kind of "the answer at a cell depends only on a few neighboring cells" structure naturally points us toward dynamic programming or memoization search.

Since we want to maximize the score while keeping the total cost within k, the cost becomes a constraint that we must carry along as part of our state. The score we can achieve at a given cell is not fixed — it depends on how much budget k we still have available. Therefore, our state needs three pieces of information: the current position (i, j) and the remaining budget k. This gives us the function dfs(i, j, k), representing the maximum score reachable from the start to position (i, j) while consuming a cost of at most k.

To compute dfs(i, j, k), we think backwards. The cell (i, j) contributes its own score grid[i][j]. If grid[i][j] is non-zero, it also consumes 1 unit of cost, so we reduce the available budget to k - 1. We then look at the two cells we could have come from — (i-1, j) and (i, j-1) — and pick whichever gives the larger score. This is why we take max(a, b) and add it to the current cell's contribution.

We also need to handle the boundary cases carefully:

If the position is out of bounds, or the remaining budget k drops below 0, the path is invalid, so we return -inf. Using -inf (instead of a regular negative number) ensures that an invalid path never wins inside a max comparison, and it correctly propagates failure upward.
When we reach the starting point (0, 0), we return 0, since the problem guarantees the start has value 0 and the journey is complete.

Because many different paths share the same subproblems (the same (i, j, k) state can be reached in multiple ways), we cache the results to avoid recomputing them. This transforms an exponential brute-force search into an efficient solution.

Finally, we call dfs(m-1, n-1, k) starting from the bottom-right corner. If the returned value is still negative (i.e., -inf), it means no valid path stayed within the budget, so we return -1; otherwise, we return the computed maximum score.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Memoization Search

We define a function dfs(i, j, k) that represents the maximum score achievable when starting from the top-left corner (0, 0) and reaching position (i, j) with the remaining cost not exceeding k. We use memoization search to avoid redundant calculations of the same state.

Specifically, the implementation steps of function dfs(i, j, k) are as follows:

If the current coordinate (i, j) is out of bounds (i.e., i < 0 or j < 0), or the remaining cost k is less than 0, return negative infinity -inf to indicate that this path is invalid and cannot reach the target under the given budget.
If the current coordinate is the starting point (0, 0), return 0, indicating that the start has been successfully reached (the problem guarantees the starting point has value 0).
Calculate the score contribution res of the current cell as grid[i][j]. If the current cell's value is not 0, decrement the remaining cost k by 1, since both values 1 and 2 cost exactly 1.
Recursively compute the maximum score achievable from the cell above (i - 1, j) and the cell to the left (i, j - 1) under the updated remaining cost k, denoted as a and b respectively.
Add the current cell's contribution res to max(a, b) to obtain the maximum score reachable at the current cell, then return this value.

Finally, we call dfs(m - 1, n - 1, k) to compute the maximum score achievable when reaching the bottom-right corner with total cost not exceeding k. If the result is less than 0 (meaning it is -inf, since no valid path exists within the budget), return -1; otherwise, return the result.

To implement memoization conveniently, we use Python's @cache decorator on dfs, which automatically stores the result of each unique (i, j, k) state. After computing the answer, we call dfs.cache_clear() to release the cache and free up memory.

The time complexity is O(m × n × k) and the space complexity is O(m × n × k), where m and n are the number of rows and columns of the grid respectively, and k is the given cost budget. This is because there are at most m × n × k distinct states, and each state is computed only once thanks to memoization.

Example Walkthrough

Let's trace through a small concrete example to see how the memoization search works.

Input:

grid = [[0, 1, 2],
        [1, 2, 1]]
k = 3

So we have a 2 x 3 grid (m = 2, n = 3) and a cost budget of k = 3. We start at (0, 0) and want to reach (1, 2).

Step 1: Understand the goal

We want to call dfs(1, 2, 3) — the maximum score to reach the bottom-right cell (1, 2) with a cost no greater than 3. We compute this by thinking backwards from the destination toward the start.

Step 2: Enumerate the possible paths

Since we can only move right or down, from (0, 0) to (1, 2) there are exactly three paths. Let's lay out the cell values along each:

Path A: (0,0)→(0,1)→(0,2)→(1,2) → values 0, 1, 2, 1
Path B: (0,0)→(0,1)→(1,1)→(1,2) → values 0, 1, 2, 1
Path C: (0,0)→(1,0)→(1,1)→(1,2) → values 0, 1, 2, 1

Interestingly, all three paths pass through three non-zero cells, so each has cost = 3, which exactly meets our budget of k = 3. Let's confirm scores:

Path A: 0 + 1 + 2 + 1 = 4
Path B: 0 + 1 + 2 + 1 = 4
Path C: 0 + 1 + 2 + 1 = 4

All valid, all score 4.

Step 3: Trace the recursion for the destination cell `dfs(1, 2, 3)`

The cell (1, 2) has value 1, so:

Current contribution res = 1.
Since the value is non-zero, the remaining budget drops to k - 1 = 2.
We then explore the two predecessors with this reduced budget:
- a = dfs(0, 2, 2) (the cell above)
- b = dfs(1, 1, 2) (the cell to the left)
Result: 1 + max(a, b).

Step 4: Expand `dfs(0, 2, 2)` — cell value `2`

res = 2, value is non-zero so budget becomes 1.
Predecessors with budget 1:
- dfs(-1, 2, 1) → out of bounds → -inf
- dfs(0, 1, 1) → cell (0,1) value 1, budget becomes 0
  - Predecessors: dfs(-1, 1, 0) = -inf, and dfs(0, 0, 0) = 0 (the start!)
  - Returns 1 + max(-inf, 0) = 1
So dfs(0, 2, 2) = 2 + max(-inf, 1) = 3.

Step 5: Expand `dfs(1, 1, 2)` — cell value `2`

res = 2, value is non-zero so budget becomes 1.
Predecessors with budget 1:
- dfs(0, 1, 1) → already cached from Step 4 → returns 1
- dfs(1, 0, 1) → cell (1,0) value 1, budget becomes 0
  - Predecessors: dfs(0, 0, 0) = 0, dfs(1, -1, 0) = -inf
  - Returns 1 + max(0, -inf) = 1
So dfs(1, 1, 2) = 2 + max(1, 1) = 3.

Notice how dfs(0, 1, 1) was reused here instead of recomputed — that is exactly the benefit memoization gives us.

Step 6: Combine at the destination

Back at dfs(1, 2, 3):

1 + max(dfs(0, 2, 2), dfs(1, 1, 2))
= 1 + max(3, 3)
= 4

Step 7: Final answer

dfs(1, 2, 3) = 4, which is >= 0, so we return 4 — matching our manual path enumeration.

What if the budget were smaller?

Suppose k = 2 instead. Every path needs cost 3, so when the recursion reaches the destination it would keep subtracting until the budget goes negative, returning -inf along every branch. The final value stays negative, so we would return -1, correctly signaling that no valid path fits within the tighter budget.

Solution Implementation

1class Solution:
2    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
3        rows, cols = len(grid), len(grid[0])
4
5        @cache
6        def dfs(row: int, col: int, remaining: int) -> int:
7            # Out of bounds or budget exhausted -> invalid path
8            if row < 0 or col < 0 or remaining < 0:
9                return -inf
10            # Reached the starting cell: base case with score 0
11            if row == 0 and col == 0:
12                return 0
13
14            # Start with the current cell's value
15            score = grid[row][col]
16            # A non-zero cell consumes one unit of the budget
17            if grid[row][col]:
18                remaining -= 1
19
20            # Move from the cell above or from the cell to the left
21            from_top = dfs(row - 1, col, remaining)
22            from_left = dfs(row, col - 1, remaining)
23            score += max(from_top, from_left)
24
25            return score
26
27        # Compute the best path score ending at the bottom-right corner
28        ans = dfs(rows - 1, cols - 1, k)
29        # Release cached results to free memory between test cases
30        dfs.cache_clear()
31
32        # Return -1 if no valid path exists within the budget
33        return -1 if ans < 0 else ans
34

1class Solution {
2    // The input grid stored as a field for easy access during recursion.
3    private int[][] grid;
4    // Memoization cache: memo[i][j][k] caches the best score reaching (i, j)
5    // from (0, 0) using budget k. Integer is used so null marks "uncomputed".
6    private Integer[][][] memo;
7    // A large negative sentinel representing an unreachable / invalid state.
8    private final int NEG_INF = -(1 << 30);
9
10    public int maxPathScore(int[][] grid, int k) {
11        this.grid = grid;
12        int rows = grid.length;
13        int cols = grid[0].length;
14
15        // Allocate the cache; the k dimension ranges from 0 to k inclusive.
16        memo = new Integer[rows][cols][k + 1];
17
18        // Start the search from the bottom-right corner with the full budget.
19        int answer = dfs(rows - 1, cols - 1, k);
20
21        // A negative result means no valid path exists, return -1 in that case.
22        return answer < 0 ? -1 : answer;
23    }
24
25    /**
26     * Computes the maximum path score to reach cell (row, col) from the
27     * top-left corner (0, 0), moving only down or right, given remaining
28     * budget k for visiting cells with a positive value.
29     *
30     * @param row the current row index
31     * @param col the current column index
32     * @param k   the remaining budget for positive-valued cells
33     * @return the maximum achievable score, or NEG_INF if the state is invalid
34     */
35    private int dfs(int row, int col, int k) {
36        // Out of bounds or budget exhausted: this state is invalid.
37        if (row < 0 || col < 0 || k < 0) {
38            return NEG_INF;
39        }
40
41        // Reached the starting cell: base case contributes a score of 0.
42        if (row == 0 && col == 0) {
43            return 0;
44        }
45
46        // Return the cached result if this state was already computed.
47        if (memo[row][col][k] != null) {
48            return memo[row][col][k];
49        }
50
51        // Add the current cell's value to the accumulated score.
52        int result = grid[row][col];
53
54        // Spend one unit of budget if the current cell has a positive value.
55        int nextK = k;
56        if (grid[row][col] > 0) {
57            --nextK;
58        }
59
60        // Explore both predecessors: the cell above and the cell to the left.
61        int fromTop = dfs(row - 1, col, nextK);
62        int fromLeft = dfs(row, col - 1, nextK);
63
64        // Take the better of the two incoming paths.
65        result += Math.max(fromTop, fromLeft);
66
67        // Cache and return the computed score for this state.
68        memo[row][col][k] = result;
69        return result;
70    }
71}
72

1class Solution {
2public:
3    int maxPathScore(vector<vector<int>>& grid, int k) {
4        int rows = grid.size();
5        int cols = grid[0].size();
6        const int INF = 1 << 30;
7
8        // memo[i][j][remaining] = max accumulated score to reach cell (i, j)
9        // from the origin (0, 0), given 'remaining' positive cells still allowed.
10        // Initialized to -1 to indicate an uncomputed state.
11        vector memo(rows, vector(cols, vector<int>(k + 1, -1)));
12
13        // dfs returns the maximum score along a path from (0, 0) to (i, j),
14        // where 'remaining' is the budget for the number of positive cells used.
15        auto dfs = [&](this auto&& dfs, int i, int j, int remaining) -> int {
16            // Out of bounds or the positive-cell budget is exhausted:
17            // return a very small value so this path is never chosen.
18            if (i < 0 || j < 0 || remaining < 0) {
19                return -INF;
20            }
21            // Reached the origin: base case with zero accumulated score.
22            if (i == 0 && j == 0) {
23                return 0;
24            }
25            // Return the cached result if this state was already computed.
26            if (memo[i][j][remaining] != -1) {
27                return memo[i][j][remaining];
28            }
29
30            // Score contributed by the current cell.
31            int result = grid[i][j];
32
33            // Spend one unit of budget if the current cell is positive.
34            int nextRemaining = remaining;
35            if (grid[i][j] > 0) {
36                --nextRemaining;
37            }
38
39            // Explore the two predecessors: from above and from the left.
40            int fromTop = dfs(i - 1, j, nextRemaining);
41            int fromLeft = dfs(i, j - 1, nextRemaining);
42            result += max(fromTop, fromLeft);
43
44            // Cache and return the best score for this state.
45            return memo[i][j][remaining] = result;
46        };
47
48        // Compute the answer starting from the bottom-right cell.
49        int answer = dfs(rows - 1, cols - 1, k);
50
51        // A negative result means no valid path exists within the budget.
52        return answer < 0 ? -1 : answer;
53    }
54};
55

1/**
2 * Finds the maximum path score from (0,0) to (m-1, n-1) moving only down or right.
3 * Each non-zero cell consumes one unit of the budget k. Returns -1 if no valid path exists.
4 *
5 * @param grid - 2D grid of non-negative integers
6 * @param k    - budget for the number of non-zero cells allowed on the path
7 * @returns    - maximum achievable path sum, or -1 if unreachable within budget
8 */
9function maxPathScore(grid: number[][], k: number): number {
10    const rows = grid.length;
11    const cols = grid[0].length;
12    // A large value used to represent an invalid (unreachable) state.
13    const infinity = 1 << 30;
14
15    // Memoization table: memo[i][j][remaining] caches the best score
16    // reaching (i, j) with `remaining` budget; -1 means "not computed yet".
17    const memo: number[][][] = Array.from({ length: rows }, () =>
18        Array.from({ length: cols }, () => Array(k + 1).fill(-1)),
19    );
20
21    /**
22     * Computes the maximum score to reach cell (i, j) from the origin,
23     * given `remaining` budget for non-zero cells.
24     *
25     * @param i         - current row index
26     * @param j         - current column index
27     * @param remaining - remaining budget for non-zero cells
28     * @returns the best score, or -infinity if the state is invalid
29     */
30    const dfs = (i: number, j: number, remaining: number): number => {
31        // Out of bounds or budget exhausted -> invalid state.
32        if (i < 0 || j < 0 || remaining < 0) {
33            return -infinity;
34        }
35        // Reached the origin; base case with score 0.
36        if (i === 0 && j === 0) {
37            return 0;
38        }
39        // Return cached result if already computed.
40        if (memo[i][j][remaining] !== -1) {
41            return memo[i][j][remaining];
42        }
43
44        // Start with the current cell's value.
45        let result = grid[i][j];
46
47        // A non-zero cell consumes one unit of budget for predecessors.
48        let nextRemaining = remaining;
49        if (grid[i][j] !== 0) {
50            --nextRemaining;
51        }
52
53        // Best score arriving from above or from the left.
54        const fromTop = dfs(i - 1, j, nextRemaining);
55        const fromLeft = dfs(i, j - 1, nextRemaining);
56        result += Math.max(fromTop, fromLeft);
57
58        // Cache and return.
59        memo[i][j][remaining] = result;
60        return result;
61    };
62
63    const answer = dfs(rows - 1, cols - 1, k);
64    // A negative result means no valid path exists within the budget.
65    return answer < 0 ? -1 : answer;
66}
67

Time and Space Complexity

Time Complexity: O(m × n × k), where m and n are the number of rows and columns in the grid, and k is the maximum allowed cost. The recursive function dfs(i, j, k) is memoized via @cache, so each distinct combination of state (i, j, k) is computed only once. The parameter i ranges over m values, j over n values, and k over O(k) values, yielding O(m × n × k) distinct states. Each state performs O(1) work (two recursive lookups and a constant number of arithmetic and comparison operations), so the overall time complexity is O(m × n × k).
Space Complexity: O(m × n × k). The memoization cache stores the result for every distinct state (i, j, k), requiring O(m × n × k) space. The recursion depth is bounded by O(m + n), which is dominated by the cache size. Therefore, the total space complexity is O(m × n × k).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Mishandling the Starting Cell's Cost When It Is Non-Zero

The base case dfs(0, 0, remaining) unconditionally returns 0, which silently assumes the starting cell (0, 0) always has value 0. While the problem statement guarantees this, relying on that assumption makes the code fragile. If the constraint ever changes—or if you reuse this logic for a similar problem where (0, 0) can be 1 or 2—the score and cost of the starting cell are completely ignored, producing incorrect results.

Why it happens: The recursion deducts cost and adds score for cell (row, col) before recursing into its predecessors. But when it finally reaches (0, 0), it short-circuits with return 0, never accounting for grid[0][0]'s own contribution or cost.

Solution: Treat the starting cell symmetrically by folding its score and cost into the base case:

@cache
def dfs(row: int, col: int, remaining: int) -> int:
    if row < 0 or col < 0 or remaining < 0:
        return -inf
    if row == 0 and col == 0:
        # Account for the starting cell explicitly
        if grid[0][0] and remaining < 1:
            return -inf
        return grid[0][0]

    score = grid[row][col]
    if grid[row][col]:
        remaining -= 1
    return score + max(dfs(row - 1, col, remaining), dfs(row, col - 1, remaining))

This guarantees correctness regardless of the value at (0, 0).

Pitfall 2: Confusing "Remaining Budget" with "Cost Already Spent"

The state parameter remaining decreases as the path is reconstructed backward. A frequent mistake is to instead track cost already consumed and compare it against k at the end. When mixing the two mental models, developers often write checks like remaining > k or forget to subtract before recursing, leading to off-by-one errors or budgets that are over/under-counted.

Why it happens: Because the DFS walks backward (from (m-1, n-1) to (0, 0)), the decrement of remaining at each non-zero cell can feel counterintuitive—it looks like we're "spending" before we've "arrived."

Solution: Be explicit and consistent. The invariant here is: remaining is the budget still available for cells (0,0) through (row, col) inclusive. Validate this with a small trace:

# grid = [[0,1],[2,0]], k = 1
# dfs(1,1,1): cell=0 -> remaining stays 1
#   dfs(0,1,1): cell=1 -> remaining=0 -> dfs(0,0,0)=0 -> score 1
#   dfs(1,0,1): cell=2 -> remaining=0 -> dfs(0,0,0)=0 -> score 2  ✓
# Answer = 2 (path 0 -> 2 -> 0)

If you prefer the forward mental model, pass cost_used and check cost_used > k early instead—but never mix the two within one function.

Pitfall 3: Forgetting `cache_clear()` Across Multiple Test Cases

The @cache decorator stores results keyed by (row, col, remaining). These keys do not include the grid itself. On platforms (or unit tests) that instantiate the Solution class once and call maxPathScore repeatedly with different grids, stale cached values from a previous grid can leak into a new call, yielding silently wrong answers.

Why it happens: @cache is attached to the function object, which persists across method invocations on the same instance. The cache cannot distinguish "same coordinates, different grid."

Solution: Always call dfs.cache_clear() after computing the answer (as the provided code correctly does), or define dfs inside maxPathScore so a fresh closure—and thus a fresh cache—is created on every call. The provided solution already does both (local definition + explicit clear), which is the safest combination.

Pitfall 4: Returning `-inf` Instead of `-1`, or Misjudging the Validity Check

The final check return -1 if ans < 0 else ans works only because a valid path always yields a non-negative score (all cell scores are ≥ 0). A subtle trap arises if you later modify scoring to allow negative contributions: then a legitimately reachable path could have a negative total score, and ans < 0 would wrongly report -1.

Why it happens: The code conflates "unreachable" (-inf) with "negative score" by using a single < 0 comparison.

Solution: Distinguish unreachability explicitly rather than relying on the sign:

ans = dfs(rows - 1, cols - 1, k)
dfs.cache_clear()
return -1 if ans == -inf else ans

Comparing against -inf directly is robust regardless of how the per-cell scoring rules evolve.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering