Skip to content

2304. Minimum Path Cost in a Grid 👍

  • Time: $O(mn^2)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
    const int m = grid.size();
    const int n = grid[0].size();
    // dp[i][j] := the minimum cost to reach grid[i][j]
    vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
    dp[0] = grid[0];

    for (int i = 1; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
          dp[i][j] = min(dp[i][j], dp[i - 1][k] + moveCost[grid[i - 1][k]][j] +
                                       grid[i][j]);

    return ranges::min(dp.back());
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int minPathCost(int[][] grid, int[][] moveCost) {
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[i][j] := the minimum cost to reach grid[i][j]
    int[][] dp = new int[m][n];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    dp[0] = grid[0];

    for (int i = 1; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);

    return Arrays.stream(dp[m - 1]).min().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minPathCost(
      self,
      grid: list[list[int]],
      moveCost: list[list[int]],
  ) -> int:
    m = len(grid)
    n = len(grid[0])
    # dp[i][j] := the minimum cost to reach grid[i][j]
    dp = [[math.inf] * n for _ in range(m)]
    dp[0] = grid[0]

    for i in range(1, m):
      for j in range(n):
        for k in range(n):
          dp[i][j] = min(dp[i][j], dp[i - 1][k] +
                         moveCost[grid[i - 1][k]][j] + grid[i][j])

    return min(dp[-1])