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, according to their cell values:
Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.
Note: If you reach the last cell but the total cost exceeds k, the path is invalid.
Example 1:
Input: grid = [[0, 1],[2, 0]], k = 1
Output: 2
Explanation:
The optimal path is:
| Cell | grid[i][j] | Score | Total Score |
Cost | Total Cost |
|---|---|---|---|---|---|
| (0, 0) | 0 | 0 | 0 | 0 | 0 |
| (1, 0) | 2 | 2 | 2 | 1 | 1 |
| (1, 1) | 0 | 0 | 2 | 0 | 1 |
Thus, the maximum possible score is 2.
Example 2:
Input: grid = [[0, 1],[1, 2]], k = 1
Output: -1
Explanation:
There is no path that reaches cell (1, 1) without exceeding cost k. Thus, the answer is -1.
Constraints:
1 <= m, n <= 2000 <= k <= 103grid[0][0] == 00 <= grid[i][j] <= 2Problem Overview: You are given a matrix where each cell contributes to a score. Starting from the top-left cell, move through the grid to reach the destination while maximizing the total score collected along the path.
Approach 1: Brute Force DFS (Exponential Time)
The most direct way is to explore every possible path from the starting cell to the destination using depth-first search. From each position, recursively move to the allowed neighboring cells (commonly right or down in grid path problems) and track the cumulative score. At the destination, return the final score and propagate the maximum back up the recursion stack. This approach checks every possible path combination, which leads to O(2^(m+n)) time in the worst case and O(m+n) recursion stack space. It demonstrates the core idea but quickly becomes infeasible for larger grids.
Approach 2: Memoization Search (Top-Down Dynamic Programming) (O(m*n))
A better approach stores intermediate results so each grid cell is solved only once. Use a DFS function dfs(r, c) that returns the maximum score obtainable starting from cell (r, c). When the function computes the result for a cell, store it in a memo table. If the same cell is reached again, return the cached value instead of recomputing all paths below it. The recurrence adds the current cell value to the maximum of the next reachable cells.
This converts the exponential search into a dynamic programming solution over the grid. Each cell becomes a state, and transitions correspond to valid moves. Because there are at most m * n cells and each state is computed once, the time complexity becomes O(m*n). The memo table requires O(m*n) space, and recursion depth is bounded by the grid dimensions.
This pattern is a classic application of dynamic programming on a matrix, where overlapping subproblems appear while exploring paths. The grid itself is simply stored as an array structure.
Recommended for interviews: Start by describing the brute-force DFS to show you understand the path enumeration. Then transition to memoization and explain how caching results for each cell eliminates repeated work. Interviewers typically expect the memoized or DP solution with O(m*n) time.
We define a function dfs(i, j, k) that represents the maximum score achievable when starting from position (i, j) and reaching the endpoint (0, 0) with remaining cost not exceeding k. We use memoization search to avoid redundant calculations.
Specifically, the implementation steps of function dfs(i, j, k) are as follows:
(i, j) is out of bounds or the remaining cost k is less than 0, return negative infinity to indicate that the endpoint cannot be reached.(0, 0), return 0, indicating that the endpoint has been reached (the problem guarantees the starting point has value 0).res of the current cell. If the current cell's value is not 0, decrement the remaining cost k by 1.(i-1, j) and the left cell (i, j-1) when reaching the endpoint with remaining cost not exceeding k, denoted as a and b respectively.res to max(a, b) to get the maximum score achievable from the current cell, and return this value.Finally, we call dfs(m-1, n-1, k) to calculate the maximum score achievable when starting from the bottom-right corner and reaching the top-left corner with remaining cost not exceeding k. If the result is less than 0, return -1 to indicate no valid path exists; otherwise, return the result.
The time complexity is O(m times n times k), and the space complexity is O(m times n times k), where m and n are the number of rows and columns in the grid, and k is the maximum allowed cost.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS | O(2^(m+n)) | O(m+n) | Conceptual baseline or very small grids where exploring all paths is feasible |
| Memoized DFS (Top-Down DP) | O(m*n) | O(m*n) | General case. Eliminates repeated subproblems and is the expected interview solution |
Maximum Path Score in a Grid | LeetCode 3742 | Weekly Contest 475 • Sanyam IIT Guwahati • 1,209 views views
Watch 4 more video solutions →Practice Maximum Path Score in a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor