3742. Maximum Path Score In A Grid

  • Array
  • Matrix
  • Dynamic Programming
TIME
O(m n min(k, m + n - 1))
SPACE
O(n * min(k, m + n - 1)) -- rolling rows
problem on leetcode ↗source on github ↗

Intuition

Grid DP with one extra dimension for the cost budget. A 2D dp[i][j] is insufficient: the budget couples decisions across the path, so we must track how much cost has been spent so far. Per cell, cost is binary (0 if value 0, else 1) and score is the cell value.

Greedy ("prefer 2s") fails, path connectivity (only right/down) forces specific cells onto every path.

Solution

State

dp[i][j][c] = maximum score reaching cell (i, j) using exactly c units of cost.

Transition

Let val = grid[i][j], cost = 0 if val == 0 else 1. From top or left:

dp[i][j][c] = val + max(dp[i-1][j][c - cost], dp[i][j-1][c - cost])

with -inf sentinels for unreachable states. c ranges from cost upward.

Base Case

dp[0][0][0] = 0 (problem guarantees grid[0][0] == 0). All other entries start at -inf.

Cost Cap

The path has exactly m + n - 1 cells, so total cost cannot exceed m + n - 1. Use K = min(k, m + n - 1) as the third-dimension size, important when k is loose (k = 1000, grid 200x200) to avoid wasted work.

Answer

max(dp[m-1][n-1][c] for c in 0..K). If all are -inf, return -1.

Space Optimization

Only the previous row is needed for transitions. Use two rolling rows of size n × (K + 1) instead of the full m × n × (K + 1) cube. Cuts memory from ~16M ints to ~80K ints for worst-case input.

Complexity

  • Time: O(m * n * min(k, m + n - 1)) worst case ≈ 200 × 200 × 399 ≈ 16M ops.
  • Space: O(n * min(k, m + n - 1)) with rolling rows.

Edge Cases

  • 1x1 grid: grid[0][0] == 0, cost 0, score 0 → return 0 regardless of k.
  • k = 0: only paths through all-zero cells are valid; otherwise -1.
  • Bottom-right cell value is 1 or 2: budget must accommodate its mandatory cost.
  • k >= m + n - 1: budget is effectively unlimited; problem reduces to plain max-score grid DP.

Code

from typing import List


class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        """
        3742. Maximum Path Score in a Grid
        Time:  O(m * n * min(k, m + n - 1))
        Space: O(n * min(k, m + n - 1))  -- rolling rows
        """
        m, n = len(grid), len(grid[0])
        K = min(k, m + n - 1)
        NEG = float("-inf")

        prev = [[NEG] * (K + 1) for _ in range(n)]
        prev[0][0] = 0  # grid[0][0] == 0 by constraint

        for j in range(1, n):
            val = grid[0][j]
            cost = 0 if val == 0 else 1
            row_prev = prev[j - 1]
            row_curr = prev[j]
            for c in range(cost, K + 1):
                left = row_prev[c - cost]
                if left != NEG:
                    row_curr[c] = left + val

        for i in range(1, m):
            curr = [[NEG] * (K + 1) for _ in range(n)]

            val0 = grid[i][0]
            cost0 = 0 if val0 == 0 else 1
            top0 = prev[0]
            cur0 = curr[0]
            for c in range(cost0, K + 1):
                top_val = top0[c - cost0]
                if top_val != NEG:
                    cur0[c] = top_val + val0

            for j in range(1, n):
                val = grid[i][j]
                cost = 0 if val == 0 else 1
                top = prev[j]
                left = curr[j - 1]
                cur = curr[j]
                for c in range(cost, K + 1):
                    t = top[c - cost]
                    l = left[c - cost]
                    best = t if t > l else l
                    if best != NEG:
                        cur[c] = best + val

            prev = curr

        ans = max(prev[n - 1])
        return int(ans) if ans != NEG else -1