Задача: 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 {
    let MAX_COST = 1000001
    var memo = [[[Int?]]](repeating: [[Int?]](repeating: [Int?](repeating: nil, count: 22), count: 102), count: 102)
    
    func findMinCost(_ houses: [Int], _ cost: [[Int]], _ targetCount: Int, _ currIndex: Int, _ neighborhoodCount: Int, _ prevHouseColor: Int) -> Int {
        if currIndex == houses.count {
            return neighborhoodCount == targetCount ? 0 : MAX_COST
        }
        
        if neighborhoodCount > targetCount {
            return MAX_COST
        }
        
        if let memoValue = memo[currIndex][neighborhoodCount][prevHouseColor] {
            return memoValue
        }
        
        var minCost = MAX_COST
        
        if houses[currIndex] != 0 {
            let newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0)
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        } else {
            for color in 1...cost[0].count {
                let newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0)
                let currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = min(minCost, currCost)
            }
        }
        
        memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
        return minCost
    }
    
    func minCost(_ houses: [Int], _ cost: [[Int]], _ m: Int, _ n: Int, _ target: Int) -> Int {
        let answer = findMinCost(houses, cost, target, 0, 0, 0)
        return answer == MAX_COST ? -1 : answer
    }
}

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