LeetCode 3742 - Maximum Path Score in a Grid

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem presents a grid of size m x n where each cell contains a value of 0, 1, or 2. Each cell contributes both a score and a cost: a cell with value 0 adds 0 to both score and cost, a cell with value 1 adds 1 to score and 1 to cost, and a cell with value 2 adds 2 to score and 1 to cost. The goal is to start from the top-left corner (0, 0) and reach the bottom-right corner (m-1, n-1) by only moving right or down, such that the total cost of the path does not exceed a given integer k. The problem asks for the maximum score achievable under this constraint, or -1 if no valid path exists.

The input consists of the grid and the integer k. The constraints indicate that the grid can be moderately large (m, n <= 200) and k can go up to 1000, so any solution with exponential complexity would not scale. Edge cases include very small grids, grids where no path satisfies the cost constraint, and grids where all values are zero or the maximum.

Approaches

The brute-force approach would be to explore every possible path from (0,0) to (m-1,n-1), calculate the cumulative score and cost, and then track the maximum score where the total cost does not exceed k. This approach is correct in principle because it considers all paths, but it is computationally infeasible because the number of paths grows exponentially with the size of the grid, roughly O(2^(m+n)).

The optimal approach leverages dynamic programming. Since movement is restricted to right or down, the problem exhibits overlapping subproblems and an optimal substructure: the maximum score to reach a cell (i,j) with a certain cost depends only on the maximum scores of the cells above (i-1,j) and to the left (i,j-1) at compatible costs. By maintaining a DP table where dp[i][j][c] represents the maximum score achievable at cell (i,j) with total cost c, we can efficiently compute the solution iteratively. This DP approach avoids redundant calculations and scales polynomially with m, n, and k.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(m+n))	O(m+n)	Explore all paths recursively; infeasible for large grids
Dynamic Programming	O(m * n * k)	O(m * n * k)	Tracks max score at each cell for all costs ≤ k; efficient

Algorithm Walkthrough

Initialize a 3D DP array dp[i][j][c] with -1 to indicate impossible states. Here i and j index the grid, and c indexes the cost used. The value will represent the maximum score at that cell with that cost.
Set the starting cell (0,0) with dp[0][0][0] = 0 because the cost of the initial cell is 0 and the score is also 0.
Iterate over each cell (i,j) in the grid.
For each valid cost c from 0 to k, check if dp[i][j][c] is reachable (i.e., not -1).
For each move (right or down), calculate the new cost new_cost = c + cost of target cell. If new_cost <= k, update the DP table at the target cell: dp[next_i][next_j][new_cost] = max(dp[next_i][next_j][new_cost], dp[i][j][c] + score of target cell).
After filling the DP table, examine all values dp[m-1][n-1][c] for c in 0..k and take the maximum score. If no valid path exists, return -1.

Why it works: Each DP state represents the maximum score achievable at a cell for a given cost. Since we explore all costs up to k, we are guaranteed to consider all feasible paths. The DP invariant ensures that at each cell, for each possible cost, we already know the best possible score that can be reached.

Python Solution

from typing import List

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        # cost_table: cost for each cell
        cost_table = [[0 if grid[i][j] == 0 else 1 for j in range(n)] for i in range(m)]
        # score_table: score for each cell
        score_table = [[grid[i][j] for j in range(n)] for i in range(m)]
        
        # Initialize dp array with -1
        dp = [[[-1]*(k+1) for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = 0
        
        for i in range(m):
            for j in range(n):
                for c in range(k+1):
                    if dp[i][j][c] == -1:
                        continue
                    # Move right
                    if j+1 < n:
                        new_cost = c + cost_table[i][j+1]
                        if new_cost <= k:
                            dp[i][j+1][new_cost] = max(dp[i][j+1][new_cost],
                                                        dp[i][j][c] + score_table[i][j+1])
                    # Move down
                    if i+1 < m:
                        new_cost = c + cost_table[i+1][j]
                        if new_cost <= k:
                            dp[i+1][j][new_cost] = max(dp[i+1][j][new_cost],
                                                        dp[i][j][c] + score_table[i+1][j])
        
        max_score = max(dp[m-1][n-1])
        return max_score if max_score != -1 else -1

The code initializes separate tables for score and cost for clarity. The main DP loop iterates through each cell and each possible cost, updating reachable states for right and down moves. The maximum score at the target cell with cost ≤ k is returned.

Go Solution

func maxPathScore(grid [][]int, k int) int {
    m, n := len(grid), len(grid[0])
    
    costTable := make([][]int, m)
    scoreTable := make([][]int, m)
    for i := 0; i < m; i++ {
        costTable[i] = make([]int, n)
        scoreTable[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if grid[i][j] == 0 {
                costTable[i][j] = 0
            } else {
                costTable[i][j] = 1
            }
            scoreTable[i][j] = grid[i][j]
        }
    }
    
    dp := make([][][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([][]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = make([]int, k+1)
            for c := 0; c <= k; c++ {
                dp[i][j][c] = -1
            }
        }
    }
    dp[0][0][0] = 0
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            for c := 0; c <= k; c++ {
                if dp[i][j][c] == -1 {
                    continue
                }
                // Right move
                if j+1 < n {
                    newCost := c + costTable[i][j+1]
                    if newCost <= k {
                        if dp[i][j+1][newCost] < dp[i][j][c] + scoreTable[i][j+1] {
                            dp[i][j+1][newCost] = dp[i][j][c] + scoreTable[i][j+1]
                        }
                    }
                }
                // Down move
                if i+1 < m {
                    newCost := c + costTable[i+1][j]
                    if newCost <= k {
                        if dp[i+1][j][newCost] < dp[i][j][c] + scoreTable[i+1][j] {
                            dp[i+1][j][newCost] = dp[i][j][c] + scoreTable[i+1][j]
                        }
                    }
                }
            }
        }
    }
    
    maxScore := -1
    for c := 0; c <= k; c++ {
        if dp[m-1][n-1][c] > maxScore {
            maxScore = dp[m-1][n-1][c]
        }
    }
    return maxScore
}

The Go implementation mirrors the Python version, using slices for the 3D DP array. The updates for each cell are done in-place with conditional checks to avoid exceeding k.

Worked Examples

Example 1: grid = [[0,1],[2,0]], k = 1

|------|-------------|---------------|--------|