Saltar al contenido

Pintar casas al menor costo

Fácil#bottom-up-dp#rolling-variables~20 min

La misión

Problema

Cada casa de una fila debe pintarse de uno de tres colores, y pintar una casa dada de un color dado tiene su propio precio. Dos casas vecinas no pueden tener el mismo color. Devuelve el precio total más barato para pintar toda la fila.

Ejemplos

Input:  costs = [[17, 2, 17],
                 [16, 16, 5],
                 [14, 3, 19]]
Output: 10
Por qué: pintas las casas con el segundo, el tercero y el segundo color por 2 + 5 + 3
Input:  costs = [[7, 6, 2]]
Output: 2
Por qué: una sola casa simplemente toma su color más barato
Input:  costs = []
Output: 0
Por qué: caso límite: una fila vacía no cuesta nada

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

Restricciones

  • each house has exactly three colour prices

¿Lo que te frena es la idea y no el código? ¿Qué es la programación dinámica? lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio