Задача
Дан двумерный массив, состоящий из нулей и единиц. Нужно найти площадь квадрата максимального размера, состоящий только из единиц.
Пример:
{"1","0","1","0","0"},
{"1","0","1","1","1"},
{"1","1","1","1","1"},
{"1","0","0","1","0"}
Ответ: 4. Тут есть несколько квадратов со стороной 1 и 2 клетки. Есть два квадрата со стороной 2 клетки. Т.е. размер стороны квадрата, максимального размера - 2. Площадь максимального квадрата - 4.
Ссылка на leetcode: https://leetcode.com/problems/maximal-square/description/
Решение.
Достаточно часто, когда в условии есть слова - найти максимальный, минимальный, оптимальный, найти число способов - это индикатор того, что задача на динамическое программирование.
Существует два подхода к решению задач на динамическое программирование:
top-down (recursion + memoization, от решения общей задачи к частным) и bottom-up (итеративный подход, от частных подзадач к решению общей задачи).
В данном случае рассмотрим bottom-up подход.
Для решения задачи bottom-up подходом нам требуется проделать 3 операции:
1) Определить состояние/решение подзадачи. Обычно, это одномерный массив dp[i] или двумерный массив dp[i][j], который определяет решение подзадачи. Например, в задаче про числа Фибоначчи, dp[i] - i-ое число Фибоначчи.
2) Определить связь решения более общей задачи с решениями подзадач. Это какая-то формула, которая связывает dp[i] с dp[i-1], dp[i-2], ... Или в двумерном случае dp[i][j] с dp[i-1][j], dp[i][j-1], dp[i-1][j-1], .... Обычно, это какая-то сумма, разность, максимум или минимум. И очень часто это еще + 1 к чему-то. В задаче, про числа Фибоначчи - это dp[i] = dp[i-1] + dp[i-2].
3) Определить базовый случай - решение тривиальной подзадачи. Обычно, это задать значение dp[0] или, dp[0][0], dp[0][1], dp[1][0] и т.д. Обычно, их надо инициализировать нулями или единицами.
Подзадачи/состояние
Одним из типичных вариантов для задания подзадачи/состояния является - решение задачи, если бы она заканчивалась в текущей точке. Например, я записывал видео решения задачи на динамическое программирование - наибольшая возрастающая подпоследовательность: https://www.youtube.com/watch?v=jSx2npfHBt0. Там случай был одномерный и dp[i] - означал размер возрастающей подпоследовательности, если бы она заканчивалась в элементе исходного массива с индексом i.
В данном случае, мы имеем дело с двумерным случаем. Поэтому нам нужно определить, что такое dp[i][j]. По аналогии с упомянутой задачей, определим dp[i][j] - решение задачи (размер квадрата), если бы он заканчивался в точке с координатами i, j. Что в данном случае означает - заканчиваться для квадрата? Это значит, что в точке i, j - правый нижний угол квадрата. Т.е. dp[i][j] - размер стороны квадрата, если бы у него был правый нижний угол в ячейке с координатами i, j.
Тогда максимум из всех dp[i][j] - будет размер наибольшего квадрата и решением задачи.
Связь задачи с подзадачами
Хорошо, мы определили, что такое dp[i][j]. Теперь, нужно определить связь между решениями более общей задачи с решениями подзадач.
Первое замечание - если в клетке у нас нолик, значит квадрат тут не может заканчиваться, поэтому dp[i][j] = 0, если arr[i][j] == "0".
Если там единица, то может. Но какого размера он будет? для этого нам надо посмотреть на соседние клетки. Причем только по диагонали влево, по горизонтали влево и по вертикали вверх. Смотреть на клетки, которые справа или снизу не надо, т.к. по определению dp[i][j] - наш квадрат должен заканчиваться в клетке (i, j).
Хорошо, а что если в одной из трех соседних клеток нолик? тогда, очевидно, квадрат не может продолжаться влево и вверх. Т.е. он будет размера 1.
Например, для клетки выделенной красным цветом, три соседние клетки выделенны зеленным. Среди них есть нолики, поэтому dp[i][j] = 1.
Давайте посмотрим другую клетку:
В трех соседних - все единички и для них значения dp - тоже равно 1. Тогда для клетки, выделенной красным цветом ответ будет 2.
Давайте посмотрим еще пример:
Слева исходный массив, справа - dp(размер стороны квадрата, который заканчивается в клетке i, j. Т.е. размер стороны квадрата, у которого правый нижний угол в клетке i, j). В клетках, соседних с красной, значение dp: 2, 1, 1. Правильным ответом, очевидно, в данном случае будет 2.
Еще одно соображение - размер квадрата, который заканчивается в клетке dp[i][j] на единицу больше, чем размер смежных квадратов. Но не всех или не всегда.
Правильным соотношением будет dp[i][j] = min(dp трех смежных клеток) + 1. Минимум нужен, т.к. квадрат нам нужно продлить во все три стороны и по какой-то из этих сторон он закончится. Это может произойти одновременно, но по одному из направлений он может оборваться раньше, т.к. встретится нолик.
Т.е. dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
Базовый кейс
Для клеток, которые находятся на границе нашей матрицы, смежными будут клетки за границами массива. Для них нужно задать значения dp[i][j] как ноль.
Реализация в коде
public int maximalSquare(char[][] matrix) {
// Искомый, максмимальный размер стороны квадрата
int maxSide = 0;
//dp[i][j] - максимальный размер стороны квадрата, который заканчивается в клетке i, j
int dp[][] = new int[matrix.length][matrix[0].length];
//Цикл по всем элементам матрицы
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
//вычисление dp[i][j]
//Обновление maxSide
}
}
}
//Нужно вернуть площадь квадрата
return maxSide * maxSide;
}
Дополним вычислением dp[i][j] и обновлением maxSide:
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
int dp[][] = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
int left = ..
int up = ...
int diagonal = ...
dp[i][j] = Math.min(Math.min(left, up), diagonal) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
Дополним вычислением значений left, up, diagonal с учетом того, что они могут быть за пределами массива:
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
int dp[][] = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
int left = j - 1 >= 0 ? dp[i][j - 1] : 0;
int up = i - 1 >= 0 ? dp[i - 1][j] : 0;
int diagonal = i - 1 >= 0 && j - 1 >= 0 ? dp[i - 1][j - 1] : 0;
dp[i][j] = Math.min(Math.min(left, up), diagonal) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
Time Complexity = O(N * M), где N - число строк в массиве. M - число столбцов. Нам нужно обойти все элементы массива, поэтому алгоритмическая сложность O(NM).
Space Complexity = O(N * M), т.к. нам надо хранить еще dp, который имеет размер такой же, как и исходный массив.
Можно убрать некрасивость в коде с проверками на границу массива. Для этого можно сделать матрицу dp на одну строку и один столбец больше. И первую строку и первый столбец выделить под смежные клетки, которые за пределами массива.
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
int dp[][] = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
int left = dp[i + 1][j];
int up = dp[i][j + 1];
int diagonal = dp[i][j];
dp[i + 1][j + 1] = Math.min(Math.min(left, up), diagonal) + 1;
maxSide = Math.max(maxSide, dp[i + 1][j + 1]);
}
}
}
return maxSide * maxSide;
}
Можно ли улучшить данное решение? Нам в любом случае придется обходить все элементы массива, поэтому алгоритмическую сложность не улучшить. А вот сложность по памяти можно улучшить, т.к. для вычисления dp[i][j] нам нужна не вся матрица dp, а только 3 смежных элемента, которые находятся в двух соседних строках. Поэтому сложность по памяти можно улучшить, но я оставлю эту оптимизацию за рамками этого разбора.
Top comments (0)