3742. Maximum Path Score in a Grid

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 <= 200
• 0 <= k <= 103​​​​​​​
• ​​​​​​​grid[0][0] == 0
• 0 <= grid[i][j] <= 2

Solutions

Solution 1: Memoization Search

We define a function \(\textit{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 \(\textit{dfs}(i, j, k)\) are as follows:

1. If the current coordinate \((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.
2. If the current coordinate is the starting point \((0, 0)\), return \(0\), indicating that the endpoint has been reached (the problem guarantees the starting point has value \(0\)).
3. Calculate the score contribution \(\textit{res}\) of the current cell. If the current cell's value is not \(0\), decrement the remaining cost \(k\) by \(1\).
4. Recursively calculate the maximum scores achievable from the upper cell \((i-1, j)\) and the left cell \((i, j-1)\) when reaching the endpoint with remaining cost not exceeding \(k\), denoted as \(\textit{a}\) and \(\textit{b}\) respectively.
5. Add the current cell's score contribution \(\textit{res}\) to \(\max(\textit{a}, \textit{b})\) to get the maximum score achievable from the current cell, and return this value.

Finally, we call \(\textit{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.

Python3JavaC++GoTypeScript

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0 or j < 0 or k < 0:
                return -inf
            if i == 0 and j == 0:
                return 0
            res = grid[i][j]
            if grid[i][j]:
                k -= 1
            a = dfs(i - 1, j, k)
            b = dfs(i, j - 1, k)
            res += max(a, b)
            return res

        ans = dfs(len(grid) - 1, len(grid[0]) - 1, k)
        dfs.cache_clear()
        return -1 if ans < 0 else ans

class Solution {
    private int[][] grid;
    private Integer[][][] f;
    private final 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 Integer[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] != null) {
            return f[i][j][k];
        }
        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;
    }
}

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int inf = 1 << 30;
        vector f(m, vector(n, vector<int>(k + 1, -1)));

        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0 || j < 0 || k < 0) {
                return -inf;
            }
            if (i == 0 && j == 0) {
                return 0;
            }
            if (f[i][j][k] != -1) {
                return f[i][j][k];
            }

            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 += max(a, b);

            return f[i][j][k] = res;
        };

        int ans = dfs(m - 1, n - 1, k);
        return ans < 0 ? -1 : ans;
    }
};

func maxPathScore(grid [][]int, k int) int {
    m := len(grid)
    n := len(grid[0])
    inf := 1 << 30

    f := make([][][]int, m)
    for i := 0; i < m; i++ {
        f[i] = make([][]int, n)
        for j := 0; j < n; j++ {
            f[i][j] = make([]int, k+1)
            for t := 0; t <= k; t++ {
                f[i][j][t] = -1
            }
        }
    }

    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i < 0 || j < 0 || k < 0 {
            return -inf
        }
        if i == 0 && j == 0 {
            return 0
        }
        if f[i][j][k] != -1 {
            return f[i][j][k]
        }

        res := grid[i][j]
        nk := k
        if grid[i][j] != 0 {
            nk--
        }

        a := dfs(i-1, j, nk)
        b := dfs(i, j-1, nk)
        res += max(a, b)

        f[i][j][k] = res
        return res
    }

    ans := dfs(m-1, n-1, k)
    if ans < 0 {
        return -1
    }
    return ans
}

function maxPathScore(grid: number[][], k: number): number {
    const m = grid.length;
    const n = grid[0].length;
    const inf = 1 << 30;

    const f: number[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => Array(k + 1).fill(-1)),
    );

    const dfs = (i: number, j: number, k: number): number => {
        if (i < 0 || j < 0 || k < 0) {
            return -inf;
        }
        if (i === 0 && j === 0) {
            return 0;
        }
        if (f[i][j][k] !== -1) {
            return f[i][j][k];
        }

        let res = grid[i][j];
        let nk = k;
        if (grid[i][j] !== 0) {
            --nk;
        }

        const a = dfs(i - 1, j, nk);
        const b = dfs(i, j - 1, nk);
        res += Math.max(a, b);

        f[i][j][k] = res;
        return res;
    };

    const ans = dfs(m - 1, n - 1, k);
    return ans < 0 ? -1 : ans;
}

Comments