Задача: 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 {
    private $MAX_COST = 1000001;
    private $memo = [];
    
    private function findMinCost($houses, $cost, $targetCount, $currIndex, $neighborhoodCount, $prevHouseColor) {
        if ($currIndex == count($houses)) {
            return $neighborhoodCount == $targetCount ? 0 : $this->MAX_COST;
        }

        if ($neighborhoodCount > $targetCount) {
            return $this->MAX_COST;
        }

        $key = "$currIndex,$neighborhoodCount,$prevHouseColor";
        if (isset($this->memo[$key])) {
            return $this->memo[$key];
        }

        $minCost = $this->MAX_COST;

        if ($houses[$currIndex] != 0) {
            $newNeighborhoodCount = $neighborhoodCount + ($houses[$currIndex] != $prevHouseColor ? 1 : 0);
            $minCost = $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $houses[$currIndex]);
        } else {
            for ($color = 1; $color <= count($cost[0]); $color++) {
                $newNeighborhoodCount = $neighborhoodCount + ($color != $prevHouseColor ? 1 : 0);
                $currCost = $cost[$currIndex][$color - 1] + $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $color);
                $minCost = min($minCost, $currCost);
            }
        }

        $this->memo[$key] = $minCost;
        return $minCost;
    }
    
    public function minCost($houses, $cost, $m, $n, $target) {
        $answer = $this->findMinCost($houses, $cost, $target, 0, 0, 0);
        return $answer == $this->MAX_COST ? -1 : $answer;
    }
}

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