Pintar casas al menor costo
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
Elegir el color más barato para cada casa por separado puede fallar, porque una elección barata puede forzar una cara en la casa de al lado. La decisión tiene que tener en cuenta lo que viene después.
Recorre la fila una vez y lleva tres respuestas acumuladas, una por color: la forma más barata de pintar todo hasta aquí si esta casa terminó de ese color.
Cada casa nueva toma su propio precio para un color y le suma la menor de las dos respuestas acumuladas de los otros dos colores. Calcula los tres valores nuevos a partir de los tres viejos a la vez, sigue adelante y quédate con el menor de los tres finales.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- each house has exactly three colour prices
Solución
Lo único que le importa al resto de la fila es el color de la casa recién pintada, así que tres totales acumulados, uno por color, capturan toda la historia. Cada casa reconstruye esos tres a partir de los tres anteriores sumando su propio precio a la más barata de las dos opciones compatibles. Calcular los tres al mismo tiempo es importante, porque usar un valor recién actualizado permitiría que una casa se apoyara en sí misma. El tiempo es O(n) y el espacio es O(1), ya que solo se guardan tres números.
def cheapest_painting(costs):
first = second = third = 0 # cheapest total ending in each of the colours
for a, b, c in costs:
# each colour pays its own price plus the better of the other two histories
first, second, third = (a + min(second, third),
b + min(first, third),
c + min(first, second))
return min(first, second, third)
print(cheapest_painting([[17, 2, 17], [16, 16, 5], [14, 3, 19]])) # -> 10
print(cheapest_painting([[7, 6, 2]])) # -> 2
print(cheapest_painting([])) # -> 0¿Lo que te frena es la idea y no el código? ¿Qué es la programación dinámica? lo explica.