Сложность: medium
Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.
Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.
Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.
Пример:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.
👨💻 Алгоритм:
1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].
2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).
😎 Решение:
class Solution {
public int minCost(int[][] costs) {
int n = costs.length;
int[][] dp = new int[n][3];
dp[0] = costs[0].clone();
for (int i = 1; i < n; i++) {
dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
}
return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
}
}Ставь 👍 и забирай 📚 Базу знаний