¿Quieres un reto mayor?
Resuelve en 15:00
Importante: Para que se registre el resultado tienes que iniciar sesión.
Este ejercicio fue usado en una prueba técnica de empleo.
Costo mínimo para pintar casas
Enunciado
Este ejercicio fue preguntado por Facebook.
Un constructor quiere edificar una fila de N casas, cada una puede pintarse de K colores distintos. Su objetivo es minimizar el costo total asegurándose de que ninguna casa adyacente tenga el mismo color.
Dada una matriz de N filas y K columnas donde el valor en la fila n y columna k representa el costo de pintar la casa n con el color k, devuelve el costo mínimo que cumple esta condición.
Ejemplo:
costs = [
[1, 2, 3],
[1, 4, 6],
[5, 2, 9]
]
Devuelve 5 ya que la combinación óptima es: casa 0 con color 0 (costo 1), casa 1 con color 2 (costo 6)... En realidad la mejor combinación es casa 0 → color 0 (1), casa 1 → color 1 (4)... pero casas adyacentes no pueden tener el mismo color. La solución óptima tiene costo 5.
Bonus: ¿Puedes resolverlo en tiempo O(N × K)?
Restriccionesexpand_more
- Dificultad: Difícil
- Completa todos los test cases para obtener los 100 puntos.
- No modificar la línea
exportal final del archivo. - Se recomienda evitar el uso de inteligencia artificial para que realmente tú practiques los ejercicios.
Puedes usar console.log() para depurar. Los resultados aparecen en la Consola de salida, no en el navegador.