Раскрасить n домов k красками
Даны n домов на улице, каждый из них может быть выкрашен в один из k цветов. Стоимость нанесения одного и того же цвета на разные дома может быть разной. Стоимость покраски довом представлена таблицей cost размером n x k. Например, costs[0][0] - это стоимость окраски дома 0 в цвет 0; costs[1][2] - стоиомсть окраски дома й в цвет 2 и т.д. Нужно раскрасить все дома так, чтобы: рядом стоящие дома были окрашены в разный цвет; стоимость всеобщаей покраски должна быть минимальной. Ограничение: все стоимости - положительные числа. Пример: Дано: [[1,5,3],[2,9,4]] Результат: 5 Объяснение: Красим дом 0 в цвет 0, дом 1 в цвет 1. Стоимость минимальна: 1 + 4 = 5; Красим дом 0 в цвет 2, дом 1 в цвет 0. Стоимость минимальна: 3 + 2 = 5; Вопрос на засыпку: можно ли решить задачу за время O(nk)? Вариант решения 1: Мемоизация Корректность входных данных. Если k = 0, значит у нас нет красок. Если нет красок, то логично предположить, что нет и домов, то есть n = 0....