We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Path Cost in a Grid

Difficulty: Medium

Problem Description

You are given a 0-indexed m x n integer matrix grid consisting of distinct integers from 0 to m * n - 1. You can move in this matrix from a cell to any other cell in the next row. That is, if you are in cell (x, y) such that x < m - 1, you can move to any of the cells (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1). Note that it is not possible to move from cells in the last row. Each possible move has a cost given by a 0-indexed 2D array moveCost of size (m * n) x n, where moveCost[i][j] is the cost of moving from a cell with value i to a cell in column j of the next row. The cost of moving from cells in the last row of grid can be ignored. The cost of a path in grid is the sum of all values of cells visited plus the sum of costs of all the moves made. Return the minimum cost of a path that starts from any cell in the first row and ends at any cell in the last row.

Key Insights

  • You can start from any cell in the first row and can move to any cell in the next row.
  • The path cost consists of two components: the sum of the values of the cells visited and the cost incurred from the moves.
  • Dynamic programming can be used to keep track of the minimum costs while transitioning from one row to the next.
  • Since moving to any cell in the next row is allowed, the problem can be solved using a grid traversal approach.

Space and Time Complexity

Time Complexity: O(m * n^2)
Space Complexity: O(n)

Solution

The solution involves using dynamic programming to keep track of the minimum cost to reach each cell in the current row based on the values and move costs from the previous row. We maintain a 1D array to store the minimum costs for the current row, which we update based on the costs from the previous row. For each cell in the current row, we calculate the cost to move from each cell in the previous row and take the minimum cost possible.

Code Solutions

def minPathCost(grid, moveCost):
    m, n = len(grid), len(grid[0])
    # Initialize the previous row costs with the values of the first row
    prev_costs = grid[0]
    
    for i in range(1, m):
        # Create a new array to store the current row costs
        current_costs = [float('inf')] * n
        
        for j in range(n):
            for k in range(n):
                # Calculate the cost of moving from previous row's cell k to current row's cell j
                move_cost = moveCost[grid[i - 1][k]][j]
                current_costs[j] = min(current_costs[j], prev_costs[k] + grid[i][j] + move_cost)
        
        # Update prev_costs to current_costs for the next iteration
        prev_costs = current_costs
    
    # Return the minimum cost from the last row
    return min(prev_costs)
← Back to All Questions