Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
👨💻 Алгоритм:
1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.
2⃣Рекурсивное вычисление минимальной стоимости:
Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома.
Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость.
3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.
😎 Решение:
class Solution:
def __init__(self):
self.MAX_COST = 1000001
self.memo = {}
def findMinCost(self, houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor):
if currIndex == len(houses):
return 0 if neighborhoodCount == targetCount else self.MAX_COST
if neighborhoodCount > targetCount:
return self.MAX_COST
if (currIndex, neighborhoodCount, prevHouseColor) in self.memo:
return self.memo[(currIndex, neighborhoodCount, prevHouseColor)]
minCost = self.MAX_COST
if houses[currIndex] != 0:
newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor)
minCost = self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
else:
for color in range(1, len(cost[0]) + 1):
newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor)
currCost = cost[currIndex][color - 1] + self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
minCost = min(minCost, currCost)
self.memo[(currIndex, neighborhoodCount, prevHouseColor)] = minCost
return minCost
def minCost(self, houses, cost, m, n, target):
answer = self.findMinCost(houses, cost, target, 0, 0, 0)
return -1 if answer == self.MAX_COST else answer
Ставь 👍 и забирай 📚 Базу знаний