Medium

Minimum Path Cost in a Grid

LAB

Move from any top-row cell to the bottom row. Moving from value v to column c costs moveCost[v][c]. Return the minimum path cost including visited cell values.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      5,
      3
    ],
    [
      4,
      0
    ],
    [
      2,
      1
    ]
  ],
  "moveCost": [
    [
      9,
      8
    ],
    [
      1,
      5
    ],
    [
      10,
      12
    ],
    [
      18,
      6
    ],
    [
      2,
      4
    ],
    [
      14,
      3
    ]
  ]
}

Output
17

FUNCTION SHAPE

grid: intMatrixmoveCost: intMatrix→int

SOLUTION NOTE

From each cell, try all columns in next row. Cost = cell value + move cost + future cost.

Reveal reference solution +

pythonREFERENCE

def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    @cache
    def dp(i, j):
        if i == m - 1:
            return grid[i][j]
        val = grid[i][j]
        return grid[i][j] + min(moveCost[val][k] + dp(i + 1, k) for k in range(n))

    return min(dp(0, j) for j in range(n))

TimeO(m × n²)

SpaceO(m × n)

Open on LeetCode ↗