Minimum cost path with alternating directions ii

Array Dynamic Programming Matrix

44.6% acceptance

Feb 25, 2026

You are given two integers m and n representing the number of rows and columns of a grid, respectively. The cost to enter cell (i, j) is defined as (i + 1) * (j + 1). You are also given a 2D integer array waitCost where waitCost[i][j] defines the cost to wait on that cell. The path will always begin by entering cell (0, 0) on move 1 and paying the entrance cost. At each step, you follow an alternating pattern: On odd-numbered seconds, you must move right or down to an adjacent cell, paying its entry cost. On even-numbered seconds, you must wait in place for exactly one second and pay waitCost[i][j] during that second. Return the minimum total cost required to reach (m - 1, n - 1).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(m: i32, n: i32, wait_cost: Vec<Vec<i32>>) -> i64 {
    let (m, n) = (m as usize, n as usize);
    let inf = i64::MAX / 2;
    let mut dp = vec![vec![inf; n]; m];
    dp[0][0] = 1; // entry cost (0+1)*(0+1) = 1
    for i in 0..m {
      for j in 0..n {
        if dp[i][j] == inf { continue; }
        let cur = dp[i][j];
        // Transition: from (i,j) we wait (paying wait_cost[i][j]) then move
        // But not at destination (m-1, n-1)
        if i == m - 1 && j == n - 1 { continue; }
        // No wait cost from (0,0): we start there before second 1 (first odd).
        // All other cells: we arrived at them on an odd second, so we must
        // wait on the next even second before moving again.
        let wait = if i == 0 && j == 0 { 0 } else { wait_cost[i][j] as i64 };
        // Move down
        if i + 1 < m {
          let entry = ((i + 2) * (j + 1)) as i64;
          let cost = cur + wait + entry;
          if cost < dp[i + 1][j] { dp[i + 1][j] = cost; }
        }
        // Move right
        if j + 1 < n {
          let entry = ((i + 1) * (j + 2)) as i64;
          let cost = cur + wait + entry;
          if cost < dp[i][j + 1] { dp[i][j + 1] = cost; }
        }
      }
    }
    dp[m - 1][n - 1]
  }
}