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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Path Cost in a Grid

Number: 1394

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n grid of distinct integers and a moveCost matrix, the task is to find the minimum path cost starting from any cell in the first row and ending at any cell in the last row. You may move from a cell (x, y) to any cell in the next row, incurring a movement cost specified in moveCost. The total cost is the sum of visited cell values and the corresponding move costs.

Key Insights

  • Use Dynamic Programming to keep track of minimum costs reaching each cell.
  • Use a 2D DP table (or 1D array optimization) where dp[i][j] represents the minimum cost reaching cell (i, j).
  • Transition from row i to row i+1 by considering every column move and adding the cost of movement.
  • The solution requires iterating row by row, and for each cell, checking all possible moves to the next row.

Space and Time Complexity

Time Complexity: O(m * n^2) where for each row (m) we consider n possible starting columns and for each we examine n possible moves. Space Complexity: O(m * n) for the DP table (can be optimized to O(n) using two arrays).

Solution

We solve this problem using dynamic programming. Initialize a dp array representing the costs of starting from the first row (which are simply the cell values). For each subsequent row, compute a new dp array where each element dp_next[j] for cell (i+1, j) is the minimum over all possible moves from any cell in the previous row i of (current cost + move cost from that cell to column j + value at grid[i+1][j]). After processing all rows, the answer will be the minimum value in the last computed dp array. The key trick is to consider the moveCost using the grid value as an index to access the additional cost to move to a particular column.

Code Solutions

# Python Solution

def minPathCost(grid, moveCost):
    # m: number of rows, n: number of columns
    m, n = len(grid), len(grid[0])
    # dp represents the minimal cost to reach each cell in the current row
    dp = grid[0][:]  # starting from the first row, cost is the grid value itself
    
    # Iterate through each row except the last one
    for i in range(1, m):
        dp_next = [float('inf')] * n  # initialize next row cost with a large value
        # For each cell in the previous row, try every possible move in the next row
        for j in range(n):
            for k in range(n):
                # Calculate cost from dp[j] to column k in row i
                cost = dp[j] + moveCost[grid[i-1][j]][k] + grid[i][k]
                dp_next[k] = min(dp_next[k], cost)
        dp = dp_next  # update dp for next iteration
    
    # The final answer is the minimum cost in the last row
    return min(dp)

# Example usage:
grid = [[5,3],[4,0],[2,1]]
moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
print(minPathCost(grid, moveCost))  # Output should be 17
← Back to All Questions