Задача: 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 = `${currIndex},${neighborhoodCount},${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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний