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>& grid, vector>& moveCost) { const int m = grid.size(); const int n = grid[0].size(); // dp[i][j] := min cost to reach grid[i][j] vector> dp(m, vector(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 *min_element(begin(dp.back()), end(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] := min 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 class Solution: def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) # dp[i][j] := min 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])