3742. Maximum Path Score in a Grid

Time: O(m*n*k)

Space: O(m*n*k)

Intuition

You can only move right or down, so every path has a fixed length. The twist is a budget k: passing through a positive cell costs 1. Recurse backwards from (m-1,n-1) — state (i,j,k) = max score from here to the destination with k budget left. Each cell adds its value and delegates to the best predecessor.

Algorithm

1Recurse from (m-1, n-1) back to (0, 0), moving only up or left.
2Base case: (0, 0) returns 0.
3Out-of-bounds or k < 0: return -∞ (impossible path sentinel).
4If grid[i][j] > 0, decrement budget: nk = k - 1.
5Result = grid[i][j] + max(Dfs(i-1, j, nk), Dfs(i, j-1, nk)).
6Memoize in f[i][j][k]. If final answer < 0, return -1.

Example Walkthrough

Input: grid = [[-1, 2], [3, -4]], k = 1

1.At (1,1): grid=-4, not positive, budget unchanged.
2.Dfs(0,1,k): grid=2 positive → nk=k-1. Only predecessor (0,0)=0. Score=2.
3.Dfs(1,0,k): grid=3 positive → nk=k-1. Only predecessor (0,0)=0. Score=3.
4.At (1,1): -4 + max(2, 3) = -1.

Output: -1

Common Pitfalls

•Sentinel must be -(1<<30), not -1 — it must survive Math.Max without polluting valid negative scores.
•Budget decrements only for strictly positive cells (> 0), not zero or negative.
•Return -1 only after full DFS; do not short-circuit on intermediate negative values.

3742.cs

// Approach: Top-down DFS with memoization. Recurse backwards from (m-1,n-1) to (0,0).
// State Dfs(i,j,k) = max score reachable with k positive-cell budget remaining.
// Decrement k only when stepping on a positive cell. Take max of up/left predecessors.
// Sentinel -inf marks impossible paths; return -1 if final answer < 0.
// Time: O(m*n*k) Space: O(m*n*k)
public class Solution
{
    private int[][] grid;
    private int?[,,] f;
    private readonly int inf = 1 << 30;

    public int MaxPathScore(int[][] grid, int k)
    {
        this.grid = grid;
        int m = grid.Length;
        int n = grid[0].Length;
        f = new int?[m, n, k + 1];
        int ans = Dfs(m - 1, n - 1, k);
        return ans < 0 ? -1 : ans;
    }

    private int Dfs(int i, int j, int k)
    {
        if (i < 0 || j < 0 || k < 0)
            return -inf;

        if (i == 0 && j == 0)
            return 0;

        if (f[i, j, k].HasValue)
            return f[i, j, k].Value;

        int res = grid[i][j];
        int nk = k;
        if (grid[i][j] > 0)
            --nk;

        int a = Dfs(i - 1, j, nk);
        int b = Dfs(i, j - 1, nk);
        res += Math.Max(a, b);
        f[i, j, k] = res;
        return res;
    }
}

Was this solution helpful?