Camino más barato por una cuadrícula
La misión
Problema
Una cuadrícula tiene un costo no negativo en cada celda. Empiezas en la celda superior izquierda y debes llegar a la celda inferior derecha, moviéndote solo hacia la derecha o hacia abajo. Devuelve la menor suma posible de los costos de las celdas por las que pasas, incluidas la primera y la última.
Ejemplos
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Por qué: derecha, derecha, abajo, abajo visita 1, 3, 1, 1, 1 y evita el 5 del centro
Input: grid = [[2, 1, 4], [3, 1, 1]]
Output: 5
Por qué: derecha, abajo, derecha visita 2, 1, 1, 1
Input: grid = [[7]]
Output: 7
Por qué: caso límite: el inicio también es la meta
Pistas
0 / 3
Elegir el vecino más barato en cada paso es una trampa, ya que un paso barato puede llevar a una zona cara. La cantidad de caminos crece demasiado rápido para probarlos todos.
Solo se puede entrar a una celda desde la celda de arriba o desde la de su izquierda. Así que el costo mínimo para llegar a una celda es su propio costo más el menor de esos dos costos mínimos.
Construye una tabla del tamaño de la cuadrícula. La entrada superior izquierda es su propio costo, la primera fila solo puede venir de la izquierda y la primera columna solo de arriba. Cada una de las demás entradas es su costo más el mínimo entre la entrada de arriba y la de la izquierda. La respuesta es la entrada inferior derecha.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(rows · cols)
Restricciones
- every cell cost is non-negative
Solución
Todo camino hacia una celda llega desde arriba o desde la izquierda, así que la forma más barata de llegar a ella extiende la más barata de esas dos formas. Llenar la tabla fila por fila garantiza que ambos vecinos sean definitivos antes de que una celda los necesite. La primera fila y la primera columna tienen una sola forma de entrar, y por eso se manejan aparte. El tiempo es O(rows · cols) y el espacio es O(rows · cols), y como cada fila solo lee la fila de arriba, basta con una sola fila de la tabla si la memoria importa.
def cheapest_path(grid):
rows, cols = len(grid), len(grid[0])
cost = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
cost[r][c] = grid[r][c]
elif r == 0:
cost[r][c] = cost[r][c - 1] + grid[r][c] # top row: only from the left
elif c == 0:
cost[r][c] = cost[r - 1][c] + grid[r][c] # left column: only from above
else:
cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
return cost[-1][-1]
print(cheapest_path([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # -> 7
print(cheapest_path([[2, 1, 4], [3, 1, 1]])) # -> 5
print(cheapest_path([[7]])) # -> 7¿Lo que te frena es la idea y no el código? DP en cuadrículas lo explica.