🔒Открыть пост
и посмотреть медиа
Задача: 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 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;
}
}
Ставь 👍 и забирай 📚 Базу знаний
