Maximum path score in a grid

Array Dynamic Programming Matrix

36.6% acceptance

Feb 25, 2026

105

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_path_score(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let k = k as usize;
    // dp[i][j][c] = max score reaching (i,j) with cost c, or -1 if unreachable
    let mut dp = vec![vec![vec![-1i32; k + 1]; n]; m];
    dp[0][0][0] = 0;
    for i in 0..m {
      for j in 0..n {
        for c in 0..=k {
          if dp[i][j][c] < 0 { continue; }
          let cur = dp[i][j][c];
          // Try moving right
          if j + 1 < n {
            let v = grid[i][j + 1];
            let cost = if v > 0 { 1 } else { 0 };
            if c + cost <= k {
              dp[i][j + 1][c + cost] = dp[i][j + 1][c + cost].max(cur + v);
            }
          }
          // Try moving down
          if i + 1 < m {
            let v = grid[i + 1][j];
            let cost = if v > 0 { 1 } else { 0 };
            if c + cost <= k {
              dp[i + 1][j][c + cost] = dp[i + 1][j][c + cost].max(cur + v);
            }
          }
        }
      }
    }
    let mut ans = -1;
    for c in 0..=k {
      ans = ans.max(dp[m - 1][n - 1][c]);
    }
    ans
  }
}