Saltar al contenido

Camino más barato por una cuadrícula

Fácil#grid-dp#2d-dp~20 min

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

Tiempo objetivo
O(rows · cols)
Espacio objetivo
O(rows · cols)

Restricciones

  • every cell cost is non-negative

¿Lo que te frena es la idea y no el código? DP en cuadrículas lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio