Раскрасить n домов k красками
Даны n домов на улице, каждый из них может быть выкрашен в один из k цветов. Стоимость нанесения одного и того же цвета на разные дома может быть разной.
Стоимость покраски довом представлена таблицей cost размером n x k. Например, costs[0][0] - это стоимость окраски дома 0 в цвет 0; costs[1][2] - стоиомсть окраски дома й в цвет 2 и т.д.
Нужно раскрасить все дома так, чтобы:
Пример:
Вопрос на засыпку: можно ли решить задачу за время O(nk)?
Если k = 0, значит у нас нет красок. Если нет красок, то логично предположить, что нет и домов, то есть n = 0. То есть на вход нам должно поступить []. Эту проверку обязательно нужно сделать в начале. И вернуть 0.
А что если на вход поступает [[],[],[],[]] при k = 0 и n = 4? Конечно, это не имеет смысла, потому что предполагается, что будем красить дома, но у нас нет красок. В этом случае решения не существует и мы можем вернуть -1.
Если k = 1 (только одна краска), тогда решение существует, только если n = 1 (один дом). Результат равен стоимости окраски единственного дома единственным цветом. Иначе мы нарушаем условие, что соседние дома не могут быть одного цвета и возвращаем -1.
Если k = 2 (две краски), тогда решение существует всегда, потому что мы можем покрасить дома чередующимися урасками. Например, когда n = 5 и k = 2, у нас два свпособа покрасить дома. Любой другой способ будет нарушать условие разных цветов на соседних домах.
Но нам нужно выбрать ту раскарску, которая дост наименьшую стомость. Тут нужно просто посчитать оба варианта раскраски и выбрать тот, что стоит меньше.
Если k = 3. Рассмотрим пример, когда n = 4, а таблица стоимости такая:
[[17, 2, 17],
[8, 4, 10],
[6, 3, 19],
[4, 8, 12]]
Мы можем визуализировать все возможные варианты раскарски в виде дерева. Каждый путь из корня в листок - это один вариант раскраски:
А путь, который даст минимальную стоимость и будет результатом.
Для создания кода нам даже не нужно строить дерево. Мы можем воспользоваться рекурсией.
Допустим, у нас есть функция раскраски с 2 параметрами: номер дома и цвет. Результатом функции - это минимальная раскраска остальных домов. Например, paint(1, red) - вернет стоимость дома 1 цветом red, а также остальных домов так, чтобы соседние дома 0 и 2 не были окрашены в цвет red.
И тогда желаемый результат будет min(paint(0, "red"), paint(0, "green"), paint(0, "blue")). Мы, на самом деле, можем стартовать с любого номера дома, результат от этого не изменится.
Ниже представлен псевдокод этой рекурсивной функции, где cost - это таблица стоимости окраски домов.
Однако, этот алгоритм неэффективен, поскольку мы многократно делаем одни и те же подсчёьы. Например, стоимость окраски второго дома в синий цвет будет одна и та же вне зависимости от того, был ли первый дом покаршен в синий или зеленый цвет. На рисунке ниже обе эти ветки идентичны и окрашены в желтый цвет.
Избыточность вычислений очевидна из параметров функции paint: это просто номер дома и цвет. И среди них нет дополнительной информации о том, где в дереве находится этот подсчёт.
Чтобы решить эту проблему, мы добавим мемоизацию. Мы будем созранять промежуточные значиния в словаре, где пара (дом, цвет) - это ключ словаря, а поддерево, которое они генерируют - значение ключа. И таким образом, мы можем подсчитать жёлтое поддерево (см. рисунок выше) только 1 раз, и при возникновении повторной необходиомсти подсчёта покраски второго дома в синий цвет, мы просто возьмём это значение из словаря.
Вот визуализация того, как будет происходит подсчёт при мемоизации. Полупрозрачные кружочки показывают обращение к словарю.Поэтому для каждой комбинации (номер дома, цвет) мы считаем поддерево один раз.
Если k > 3, то алгоритм не сильно отличается от того, к чему мы сейчас пришли. Единственная разница, что на каждом шаге мы рассматриваем не оставшиеся 2 цвета, а оставшиеся k - 1 (все, кроме текущего).
Алгорим 1
Мы пронумеруем краски от 0 до k - 1 и будем использовать номер краски, а не её название.
class Solution {
private int n;
private int k;
private int[][] costs;
private Map<String, Integer> memo;
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
this.k = costs[0].length;
this.n = costs.length;
this.costs = costs;
this.memo = new HashMap<>();
int minCost = Integer.MAX_VALUE;
for (int color = 0; color < k; color++) {
minCost = Math.min(minCost, memoSolve(0, color));
}
return minCost;
}
private int memoSolve(int houseNumber, int color) {
// Base case: There are no more houses after this one.
if (houseNumber == n - 1) {
return costs[houseNumber][color];
}
// Memoization lookup case: Have we already solved this subproblem?
if (memo.containsKey(getKey(houseNumber, color))) {
return memo.get(getKey(houseNumber, color));
}
// Recursive case: Determine the minimum cost for the remainder.
int minRemainingCost = Integer.MAX_VALUE;
for (int nextColor = 0; nextColor < k; nextColor++) {
if (color == nextColor) continue;
int currentRemainingCost = memoSolve(houseNumber + 1, nextColor);
minRemainingCost = Math.min(currentRemainingCost, minRemainingCost);
}
int totalCost = costs[houseNumber][color] + minRemainingCost;
memo.put(getKey(houseNumber, color), totalCost);
return totalCost;
}
// Convert a house number and color into a simple string key for the memo.
private String getKey(int n, int color) {
return String.valueOf(n) + " " + String.valueOf(color);
}
}
Анализ сложности Алгоритма 1
Сложность по времени : O(n*k*k).
Для определения сложности по времени, нам нужно понять, сколько раз мы обращаемся к функции paint, и сколько нам стоит каждое обращение. Помним, что обращение к словарю - это констатная операция.
Функция вызывается один раз для каждой комбинации (номер дома, номер цвета). То есть k*n вызовов. Каждый вызов просматривает k цветов. Поэтому сложность по времени O(n*k*k).
Фрагмент вне рекурсивной части имеет сложность O(k) и поэтому не влияет на общую сложность алгоритма.
Сложность по памяти: O(n⋅k).
У нас есть два мечста, в которых мы должны обратить внимание на использование памяти.
Во-первых, при мемоизации мы храним ответ для каждой пары (дом, цвет). Поскольку домов у нас n, а красок - k, то их всевозможные комбинации требуют O(n⋅k) памяти.
Во-вторых, нам нужно рассмотреть память, которую мы используем в стеке исполнения алгоритма. В худшем случае, для каждого дома мы выделяем отдельный стек-фрейм. А это O(n) памяти.
Оценка O(n) незначительна по сравнению с O(n⋅k), поэтому итоговая оценка будет O(n⋅k).
[[10, 6, 16, 25, 7, 28],
[7, 16, 18, 30, 16, 25],
[8, 26, 6, 22, 26, 19],
[10, 23, 14, 17, 23, 9],
[12, 14, 27, 7, 8, 9]]
И ниже мы покажем диаграмму входной таблицы.
Каждая строка соответствует одному дому и представляет собой стоимость окраски этого дома в соответствующий цвет.
Задача, которую мы решаем, имеет эквивалентную формулировку: выбрать ровно одно число в каждой строке так, чтобы сумма этих чисел была минимальной. И поскольку 2 соседних дома не могут быть выкрашены в один цвет, соседние строки долны быть выбраны из разных столбцов. Это очевидный вариант "классической" задачи динамического программирования про минимальный-путь-в-таблице.
Мы решаем эту задачу путём обхода ячеек таблицы и определением самого дешевого способа попасть в эту ячейку. Обход делаем сверху вниз.
Начинаем с первой строки, которая соответствует дому 0. И в этой строке нам не нужно делать никаких изменений. Если у нас только дом 0, то мы выбираем наименьшее значение из первой строки.
Если у нас не только дом 0. Тогда переходим к следующей строке. И для каждой ячейки второй строки мы просчитываем наиболее дешевый вариант с учётом первой строки. Например, чтобы дойти до ячейки [1][red], мы учитываем все не-красные ячейки предыдущей строки.
Мы обновляем ячейку [1][red] минимально возможным значением 7 + 6 = 13.
Мы повторяем эту операцию для оставшихся ячеек кторой строки и затем переходим к третьей строке. И так далее.
И когда мы просчитаем все ячейки, результат будет в ячейке с минимальным значением в последней строке.
Алгорим 2
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor)
continue;
min = Math.min(min, costs[house - 1][previousColor]);
}
costs[house][color] += min;
}
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k^2).
Мы обходим n⋅k ячеек. Для каждой из ячейки, мы находим минимум из kk значенией в предыдущей строке, исключая значение в том же самом столбце. Стоимость этой операции O(k). Умножая обе стоимости, мы получаем O(n⋅k^2).
Сложность по памяти: O(1), если мы обновляем исходную таблицу, поскольку мы не создаём новых структур данных. O(n⋅k) если мы сделали копию входных данных, что иногда может быть полезно.
Но есть способ не затирать исходные данные и использовать меньше памяти. Для этого нам нужно держать в памяти две строки: ту, которую мы высчитываем, и предыдущую. И для этого нам понадобится 2k = O(k) дополнительной памяти.
Алгорим 3
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
int[] previousRow = costs[0];
for (int house = 1; house < n; house++) {
int[] currentRow = new int[k];
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor)
continue;
min = Math.min(min, previousRow[previousColor]);
}
currentRow[color] += costs[house][color] += min;
}
previousRow = currentRow;
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : previousRow) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k^2) по тем же самым соображениям, что и в Алгоритме 2
Сложность по памяти: O(k). И при этом мы не затираем входные значения.
Но давайте подумаем, а надо ли нам просматривать всю предыдущую строку целиком. Когда мы подсчитываем значения для второй строки, мы для каждой её ячейки добавляем минимальное значение из первой строки. Единственная ячейка для которой мы добавляем другое значение - это та, которая находится непосредственно под минимальным значением из первой строки, чтобы соблюсти правило разной раскраски соседних домов. И поэтому для этой ячйки мы добавляем второй минимум.
Алгорим 4
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
// Find the minimum and second minimum color in the PREVIOUS row.
int minColor = -1;
int secondMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[house - 1][color];
if (minColor == -1 || cost < costs[house - 1][minColor]) {
secondMinColor = minColor;
minColor = color;
} else if (secondMinColor == -1 || cost < costs[house - 1][secondMinColor]) {
secondMinColor = color;
}
}
// And now calculate the new costs for the current row.
for (int color = 0; color < k; color++) {
if (color == minColor) {
costs[house][color] += costs[house - 1][secondMinColor];
} else {
costs[house][color] += costs[house - 1][minColor];
}
}
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k).
Первый цикл находит минимальный элемент в строке длинны k, поэтому сложность этой операции O(k). Второй цикл имеет сложность O(n⋅k), потому что внешний цикл "прокручивается" n раз, внутренний цикл - k раз. O(n⋅k) + O(k) = O(n⋅k). Более того, мы можем сделать вывод, что нельзя улучшить скорость алгоритма, потому что нам в любом случае нужно просмотреть все ячейки входной таблицы, состоящей из n⋅k ячеек.
Сложность по памяти: O(1). Как в Алгоритме 2, мы просто модивицируем входные данные без создания новых структур.
В предыдущей версии алгоритм проходит по строкам и в каждой находит 2 минимума. Это происходит подсчётом новой цены в каждой строке, записыванием этой цены и ваявлением новых двух минимумов. Затирание исходных значений не обязательно - мы просто можем держать в памяти два самых маленьких числа, которые мы нашли: для предыдущей строки и для текущей.
Алгорим 5
Это гибрид алгоритма 3 и 4. Как в варианте 4, мы ищем минимум только один раз. И как в варианте 3, мы храним информацию о предыдущей строке. В отличие от алгоритма 3, мы храним информацию о минимумах, а не о всей строке.
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
/*
* Firstly, we need to determine the 2 lowest costs of the first row.
* We also need to remember the color of the lowest.
*/
int prevMin = -1;
int prevSecondMin = -1;
int prevMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[0][color];
if (prevMin == -1 || cost < prevMin) {
prevSecondMin = prevMin;
prevMinColor = color;
prevMin = cost;
} else if (prevSecondMin == -1 || cost < prevSecondMin) {
prevSecondMin = cost;
}
}
// And now, we need to work our way down, keeping track of the minimums.
for (int house = 1; house < n; house++) {
int min = -1;
int secondMin = -1;
int minColor = -1;
for (int color = 0; color < k; color++) {
// Determine the cost for this cell (without writing it in).
int cost = costs[house][color];
if (color == prevMinColor) {
cost += prevSecondMin;
} else {
cost += prevMin;
}
// Determine whether or not this current cost is also a minimum.
if (min == -1 || cost < min) {
secondMin = min;
minColor = color;
min = cost;
} else if (secondMin == -1 || cost < secondMin) {
secondMin = cost;
}
}
// Transfer current mins to be previous mins.
prevMin = min;
prevSecondMin = secondMin;
prevMinColor = minColor;
}
return prevMin;
}
Анализ сложности
Сложность по времени: O(n⋅k). Как в алгоритме 4.
Сложность по памяти: O(1).
Дополнительная память, которую мы используем: переменные для хранения 2 минимумов из текущей и предыдущей строки. Поскольку эта дополнительная память не увеличивается с увеличением размера входных данных, то мы можем сказать, что памятьь константна: O(1). И в отличие от предыдущего варианта, мы не затираем входную информацию.
Стоимость покраски довом представлена таблицей cost размером n x k. Например, costs[0][0] - это стоимость окраски дома 0 в цвет 0; costs[1][2] - стоиомсть окраски дома й в цвет 2 и т.д.
Нужно раскрасить все дома так, чтобы:
- рядом стоящие дома были окрашены в разный цвет;
- стоимость всеобщаей покраски должна быть минимальной.
Пример:
Дано: [[1,5,3],[2,9,4]] Результат: 5 Объяснение: Красим дом 0 в цвет 0, дом 1 в цвет 1. Стоимость минимальна: 1 + 4 = 5; Красим дом 0 в цвет 2, дом 1 в цвет 0. Стоимость минимальна: 3 + 2 = 5;
Вопрос на засыпку: можно ли решить задачу за время O(nk)?
Вариант решения 1: Мемоизация
Корректность входных данных.Если k = 0, значит у нас нет красок. Если нет красок, то логично предположить, что нет и домов, то есть n = 0. То есть на вход нам должно поступить []. Эту проверку обязательно нужно сделать в начале. И вернуть 0.
А что если на вход поступает [[],[],[],[]] при k = 0 и n = 4? Конечно, это не имеет смысла, потому что предполагается, что будем красить дома, но у нас нет красок. В этом случае решения не существует и мы можем вернуть -1.
Если k = 1 (только одна краска), тогда решение существует, только если n = 1 (один дом). Результат равен стоимости окраски единственного дома единственным цветом. Иначе мы нарушаем условие, что соседние дома не могут быть одного цвета и возвращаем -1.
Если k = 2 (две краски), тогда решение существует всегда, потому что мы можем покрасить дома чередующимися урасками. Например, когда n = 5 и k = 2, у нас два свпособа покрасить дома. Любой другой способ будет нарушать условие разных цветов на соседних домах.
Но нам нужно выбрать ту раскарску, которая дост наименьшую стомость. Тут нужно просто посчитать оба варианта раскраски и выбрать тот, что стоит меньше.
Если k = 3. Рассмотрим пример, когда n = 4, а таблица стоимости такая:
[[17, 2, 17],
[8, 4, 10],
[6, 3, 19],
[4, 8, 12]]
Мы можем визуализировать все возможные варианты раскарски в виде дерева. Каждый путь из корня в листок - это один вариант раскраски:
Для создания кода нам даже не нужно строить дерево. Мы можем воспользоваться рекурсией.
Допустим, у нас есть функция раскраски с 2 параметрами: номер дома и цвет. Результатом функции - это минимальная раскраска остальных домов. Например, paint(1, red) - вернет стоимость дома 1 цветом red, а также остальных домов так, чтобы соседние дома 0 и 2 не были окрашены в цвет red.
И тогда желаемый результат будет min(paint(0, "red"), paint(0, "green"), paint(0, "blue")). Мы, на самом деле, можем стартовать с любого номера дома, результат от этого не изменится.
Ниже представлен псевдокод этой рекурсивной функции, где cost - это таблица стоимости окраски домов.
def paint(i, color):
### простой случай ###
if i последний номер дома (мы уже рассмотерли все дома):
return costs[i][color]
### рекурсивный случай ###
lowest_cost = Infinity
for each next_color in ["red", "green", "blue"]:
if next_color != color: # соседние дома должны быть другого цвета.
this_cost = costs[i][color] + paint(i + 1, next_color) # <- РЕКУРСИВНЫЙ ВЫЗОВ
lowest_cost = min(lowest_cost, this_cost)
return lowest_cost
Однако, этот алгоритм неэффективен, поскольку мы многократно делаем одни и те же подсчёьы. Например, стоимость окраски второго дома в синий цвет будет одна и та же вне зависимости от того, был ли первый дом покаршен в синий или зеленый цвет. На рисунке ниже обе эти ветки идентичны и окрашены в желтый цвет.
Избыточность вычислений очевидна из параметров функции paint: это просто номер дома и цвет. И среди них нет дополнительной информации о том, где в дереве находится этот подсчёт.
Чтобы решить эту проблему, мы добавим мемоизацию. Мы будем созранять промежуточные значиния в словаре, где пара (дом, цвет) - это ключ словаря, а поддерево, которое они генерируют - значение ключа. И таким образом, мы можем подсчитать жёлтое поддерево (см. рисунок выше) только 1 раз, и при возникновении повторной необходиомсти подсчёта покраски второго дома в синий цвет, мы просто возьмём это значение из словаря.
Вот визуализация того, как будет происходит подсчёт при мемоизации. Полупрозрачные кружочки показывают обращение к словарю.Поэтому для каждой комбинации (номер дома, цвет) мы считаем поддерево один раз.
Если k > 3, то алгоритм не сильно отличается от того, к чему мы сейчас пришли. Единственная разница, что на каждом шаге мы рассматриваем не оставшиеся 2 цвета, а оставшиеся k - 1 (все, кроме текущего).
Алгорим 1
Мы пронумеруем краски от 0 до k - 1 и будем использовать номер краски, а не её название.
class Solution {
private int n;
private int k;
private int[][] costs;
private Map<String, Integer> memo;
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
this.k = costs[0].length;
this.n = costs.length;
this.costs = costs;
this.memo = new HashMap<>();
int minCost = Integer.MAX_VALUE;
for (int color = 0; color < k; color++) {
minCost = Math.min(minCost, memoSolve(0, color));
}
return minCost;
}
private int memoSolve(int houseNumber, int color) {
// Base case: There are no more houses after this one.
if (houseNumber == n - 1) {
return costs[houseNumber][color];
}
// Memoization lookup case: Have we already solved this subproblem?
if (memo.containsKey(getKey(houseNumber, color))) {
return memo.get(getKey(houseNumber, color));
}
// Recursive case: Determine the minimum cost for the remainder.
int minRemainingCost = Integer.MAX_VALUE;
for (int nextColor = 0; nextColor < k; nextColor++) {
if (color == nextColor) continue;
int currentRemainingCost = memoSolve(houseNumber + 1, nextColor);
minRemainingCost = Math.min(currentRemainingCost, minRemainingCost);
}
int totalCost = costs[houseNumber][color] + minRemainingCost;
memo.put(getKey(houseNumber, color), totalCost);
return totalCost;
}
// Convert a house number and color into a simple string key for the memo.
private String getKey(int n, int color) {
return String.valueOf(n) + " " + String.valueOf(color);
}
}
Анализ сложности Алгоритма 1
Сложность по времени : O(n*k*k).
Для определения сложности по времени, нам нужно понять, сколько раз мы обращаемся к функции paint, и сколько нам стоит каждое обращение. Помним, что обращение к словарю - это констатная операция.
Функция вызывается один раз для каждой комбинации (номер дома, номер цвета). То есть k*n вызовов. Каждый вызов просматривает k цветов. Поэтому сложность по времени O(n*k*k).
Фрагмент вне рекурсивной части имеет сложность O(k) и поэтому не влияет на общую сложность алгоритма.
Сложность по памяти: O(n⋅k).
У нас есть два мечста, в которых мы должны обратить внимание на использование памяти.
Во-первых, при мемоизации мы храним ответ для каждой пары (дом, цвет). Поскольку домов у нас n, а красок - k, то их всевозможные комбинации требуют O(n⋅k) памяти.
Во-вторых, нам нужно рассмотреть память, которую мы используем в стеке исполнения алгоритма. В худшем случае, для каждого дома мы выделяем отдельный стек-фрейм. А это O(n) памяти.
Оценка O(n) незначительна по сравнению с O(n⋅k), поэтому итоговая оценка будет O(n⋅k).
Вариант решения 2: Динамическое программирование
Для рассмотрения задачи с точки зрения динамического программирования, давайте расширим пример, который мы рассматривали ранее, до k = 6 и n = 5.[[10, 6, 16, 25, 7, 28],
[7, 16, 18, 30, 16, 25],
[8, 26, 6, 22, 26, 19],
[10, 23, 14, 17, 23, 9],
[12, 14, 27, 7, 8, 9]]
И ниже мы покажем диаграмму входной таблицы.
Каждая строка соответствует одному дому и представляет собой стоимость окраски этого дома в соответствующий цвет.
Задача, которую мы решаем, имеет эквивалентную формулировку: выбрать ровно одно число в каждой строке так, чтобы сумма этих чисел была минимальной. И поскольку 2 соседних дома не могут быть выкрашены в один цвет, соседние строки долны быть выбраны из разных столбцов. Это очевидный вариант "классической" задачи динамического программирования про минимальный-путь-в-таблице.
Мы решаем эту задачу путём обхода ячеек таблицы и определением самого дешевого способа попасть в эту ячейку. Обход делаем сверху вниз.
Начинаем с первой строки, которая соответствует дому 0. И в этой строке нам не нужно делать никаких изменений. Если у нас только дом 0, то мы выбираем наименьшее значение из первой строки.
Если у нас не только дом 0. Тогда переходим к следующей строке. И для каждой ячейки второй строки мы просчитываем наиболее дешевый вариант с учётом первой строки. Например, чтобы дойти до ячейки [1][red], мы учитываем все не-красные ячейки предыдущей строки.
Мы обновляем ячейку [1][red] минимально возможным значением 7 + 6 = 13.
Мы повторяем эту операцию для оставшихся ячеек кторой строки и затем переходим к третьей строке. И так далее.
И когда мы просчитаем все ячейки, результат будет в ячейке с минимальным значением в последней строке.
Алгорим 2
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor)
continue;
min = Math.min(min, costs[house - 1][previousColor]);
}
costs[house][color] += min;
}
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k^2).
Мы обходим n⋅k ячеек. Для каждой из ячейки, мы находим минимум из kk значенией в предыдущей строке, исключая значение в том же самом столбце. Стоимость этой операции O(k). Умножая обе стоимости, мы получаем O(n⋅k^2).
Сложность по памяти: O(1), если мы обновляем исходную таблицу, поскольку мы не создаём новых структур данных. O(n⋅k) если мы сделали копию входных данных, что иногда может быть полезно.
Вариант решения 3: Динамическое программирование с O(k) дополнительной памяти
Как мы обсудили выше, если мы не делаем копию исходных данных, мы модифицируем таблицу стоимостей, затирая её первоначальные значения. Если мы не хотим затирать входные значения, нам придётся сделать копию, что потребует O(n⋅k) дополнительной памяти.Но есть способ не затирать исходные данные и использовать меньше памяти. Для этого нам нужно держать в памяти две строки: ту, которую мы высчитываем, и предыдущую. И для этого нам понадобится 2k = O(k) дополнительной памяти.
Алгорим 3
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
int[] previousRow = costs[0];
for (int house = 1; house < n; house++) {
int[] currentRow = new int[k];
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor)
continue;
min = Math.min(min, previousRow[previousColor]);
}
currentRow[color] += costs[house][color] += min;
}
previousRow = currentRow;
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : previousRow) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k^2) по тем же самым соображениям, что и в Алгоритме 2
Сложность по памяти: O(k). И при этом мы не затираем входные значения.
Вариант решения 4: Динамическое программирование с оптимизированным временем
До сих пор все наши алгоритмы давали сложность по времени O(n⋅k^2). Потому что для каждой из O(n⋅k) ячеек мы просматриваем k ячеек из предыдущей строки.Но давайте подумаем, а надо ли нам просматривать всю предыдущую строку целиком. Когда мы подсчитываем значения для второй строки, мы для каждой её ячейки добавляем минимальное значение из первой строки. Единственная ячейка для которой мы добавляем другое значение - это та, которая находится непосредственно под минимальным значением из первой строки, чтобы соблюсти правило разной раскраски соседних домов. И поэтому для этой ячйки мы добавляем второй минимум.
Алгорим 4
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
// Find the minimum and second minimum color in the PREVIOUS row.
int minColor = -1;
int secondMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[house - 1][color];
if (minColor == -1 || cost < costs[house - 1][minColor]) {
secondMinColor = minColor;
minColor = color;
} else if (secondMinColor == -1 || cost < costs[house - 1][secondMinColor]) {
secondMinColor = color;
}
}
// And now calculate the new costs for the current row.
for (int color = 0; color < k; color++) {
if (color == minColor) {
costs[house][color] += costs[house - 1][secondMinColor];
} else {
costs[house][color] += costs[house - 1][minColor];
}
}
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
Анализ сложности
Сложность по времени: O(n⋅k).
Первый цикл находит минимальный элемент в строке длинны k, поэтому сложность этой операции O(k). Второй цикл имеет сложность O(n⋅k), потому что внешний цикл "прокручивается" n раз, внутренний цикл - k раз. O(n⋅k) + O(k) = O(n⋅k). Более того, мы можем сделать вывод, что нельзя улучшить скорость алгоритма, потому что нам в любом случае нужно просмотреть все ячейки входной таблицы, состоящей из n⋅k ячеек.
Сложность по памяти: O(1). Как в Алгоритме 2, мы просто модивицируем входные данные без создания новых структур.
Вариант решения 5: Динамическое программирование с оптимизированным временем и памятью
Мы можем решить задачу с O(1) памяти и O(n⋅k) скоростью, и при этом не модифицировать взодные данные.В предыдущей версии алгоритм проходит по строкам и в каждой находит 2 минимума. Это происходит подсчётом новой цены в каждой строке, записыванием этой цены и ваявлением новых двух минимумов. Затирание исходных значений не обязательно - мы просто можем держать в памяти два самых маленьких числа, которые мы нашли: для предыдущей строки и для текущей.
Алгорим 5
Это гибрид алгоритма 3 и 4. Как в варианте 4, мы ищем минимум только один раз. И как в варианте 3, мы храним информацию о предыдущей строке. В отличие от алгоритма 3, мы храним информацию о минимумах, а не о всей строке.
public int minCostII(int[][] costs) {
if (costs.length == 0)
return 0;
int k = costs[0].length;
int n = costs.length;
/*
* Firstly, we need to determine the 2 lowest costs of the first row.
* We also need to remember the color of the lowest.
*/
int prevMin = -1;
int prevSecondMin = -1;
int prevMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[0][color];
if (prevMin == -1 || cost < prevMin) {
prevSecondMin = prevMin;
prevMinColor = color;
prevMin = cost;
} else if (prevSecondMin == -1 || cost < prevSecondMin) {
prevSecondMin = cost;
}
}
// And now, we need to work our way down, keeping track of the minimums.
for (int house = 1; house < n; house++) {
int min = -1;
int secondMin = -1;
int minColor = -1;
for (int color = 0; color < k; color++) {
// Determine the cost for this cell (without writing it in).
int cost = costs[house][color];
if (color == prevMinColor) {
cost += prevSecondMin;
} else {
cost += prevMin;
}
// Determine whether or not this current cost is also a minimum.
if (min == -1 || cost < min) {
secondMin = min;
minColor = color;
min = cost;
} else if (secondMin == -1 || cost < secondMin) {
secondMin = cost;
}
}
// Transfer current mins to be previous mins.
prevMin = min;
prevSecondMin = secondMin;
prevMinColor = minColor;
}
return prevMin;
}
Анализ сложности
Сложность по времени: O(n⋅k). Как в алгоритме 4.
Сложность по памяти: O(1).
Дополнительная память, которую мы используем: переменные для хранения 2 минимумов из текущей и предыдущей строки. Поскольку эта дополнительная память не увеличивается с увеличением размера входных данных, то мы можем сказать, что памятьь константна: O(1). И в отличие от предыдущего варианта, мы не затираем входную информацию.
Комментарии
Отправить комментарий