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, according to their cell values:
- 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.
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] <= 2
Solutions
This is the most optimized and unified DP approach — it treats every cell uniformly by computing a cost (0 for free cells, 1 for collected cells) and processing all cells in a single nested loop. For each cell and each k value (iterated backward for early exit), it computes the required predecessor state nkc = kc - cost, then takes the maximum incoming path from above or left. The single unified logic eliminates separate boundary handling while maintaining backward iteration for the early-exit optimization, achieving minimal complexity and maximum clarity.
/**
* @param {number[][]} grid
* @param {number} k
* @return {number}
*/
var maxPathScore = function (grid, k) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m },
() => Array.from({ length: n },
() => Array(k + 1).fill(-Infinity)));
dp[0][0] = Array(k + 1).fill(0);
for (let row = 0; row < m; row++) {
const hasPrevRow = row > 0;
for (let col = 0; col < n; col++) {
if (row === 0 && col === 0) {
continue;
}
const hasPrevCol = col > 0;
const score = grid[row][col];
const cost = grid[row][col] === 0 ? 0 : 1;
for (let kc = k; kc >= 0; kc--) {
const nkc = kc - cost;
dp[row][col][kc] = nkc < 0 ? -Infinity : (Math.max(
hasPrevRow ? dp[row - 1][col][nkc] : -Infinity,
hasPrevCol ? dp[row][col - 1][nkc] : -Infinity,
) + score);
if (dp[row][col][kc] === -Infinity) {
break;
}
}
}
}
const max = Math.max(...dp[m - 1][n - 1]);
return max === -Infinity ? -1 : max;
};