Задача: 1473. Paint House III Сложность: 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 { constructor() { this.MAX_COST = 1000001; this.memo = new Map(); } findMinCost(houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor) { if (currIndex === houses.length) { return neighborhoodCount === targetCount ? 0 : this.MAX_COST; } if (neighborhoodCount > targetCount) { return this.MAX_COST; } const key = &#036;{currIndex},&#036;{neighborhoodCount},&#036;{prevHouseColor}; if (this.memo.has(key)) { return this.memo.get(key); } let minCost = this.MAX_COST; if (houses[currIndex] !== 0) { const newNeighborhoodCount = neighborhoodCount + (houses[currIndex] !== prevHouseColor ? 1 : 0); minCost = this.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]); } else { for (let color = 1; color <= cost[0].length; color++) { const newNeighborhoodCount = neighborhoodCount + (color !== prevHouseColor ? 1 : 0); const currCost = cost[currIndex][color - 1] + this.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color); minCost = Math.min(minCost, currCost); } } this.memo.set(key, minCost); return minCost; } minCost(houses, cost, m, n, target) { const answer = this.findMinCost(houses, cost, target, 0, 0, 0); return answer === this.MAX_COST ? -1 : answer; } } Ставь 👍 и забирай 📚 Базу знаний