Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  };
  
  

• 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
  
  

• 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;
  }
  
  

All Problems

All Solutions