Это вопрос leetcode, найденный на майской неделе испытаний 3.It Это вопрос среднего уровня, и я мог думать только о рекурсивном решении методом перебора (что, очевидно, привело к превышению лимита времени). Итак, я проверил дискуссионный форум и нашел прекрасное решение для динамического программирования, которое я был полон решимости понять!Здесь я собираюсь дать вам некоторое представление об ответе с помощью серии уродливых, но полезных рисунков. Я надеюсь, что это поможет! Вот ссылка на обсуждение, это решение от Lee215: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441306/JavaC%2B%2BPython-DP-solution Итак, если вы не проверили ссылку, вот решение и предоставленное объяснение для него: “dp [i] [j] означает размер самого большого квадрата с [i] [j] в правом нижнем углу. dp[i][j] также означает количество квадратов с [i][j] в правом нижнем углу.
Если A[i][j], то нет возможного квадрата. Если A[i][j], мы сравниваем размер квадрата dp[i-1][j-1], dp[i-1][j] и dp[i][j-1]. min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 – это максимальный размер квадрата, который мы можем найти.”
public int countSquares(int[][] A) {
int res = 0;
for (int i = 0; i < A.length; ++i) {
for (int j = 0; j < A[0].length; ++j) {
if (A[i][j] > 0 && i > 0 && j > 0) {
A[i][j] = Math.min(A[i - 1][j - 1], Math.min(A[i - 1][j], A[i][j - 1])) + 1;
}
res += A[i][j];
}
}
return res;
}
Итак, второе предложение в объяснении дискуссионного форума гласит: “dp [i] [j] означает количество квадратов с [i] [j] в правом нижнем углу. ” Итак, мы проведем цикл по каждому элементу с индексами i, j и вычислим количество квадратов, в которых этот конкретный элемент является нижним правым элементом. Элемент может участвовать во многих квадратах разных размеров, начиная с квадрата размером 1 (только этот элемент) до максимально возможного размера квадратов.
В первом предложении говорится: “dp [i][j] означает размер самого большого квадрата с [i][j] в правом нижнем углу. ” Итак, если я вычислю количество различных квадратов, в которых этот элемент находится в правом нижнем углу, следовательно, это также считается квадратом максимального размера, в котором может участвовать этот элемент.
Итак, если я вычислю количество различных квадратов, в которых этот элемент находится в правом нижнем углу, следовательно, это также считается квадратом максимального размера, в котором может участвовать этот элемент.
рассмотрим эту матрицу, где мы оцениваем элемент с индексом [1][1] “элемент в розовом поле”, Ясно, что максимальный квадрат, который этот элемент образует в правом нижнем углу, представляет собой квадрат размера 1, потому что элемент [0][0] равен ноль. Если бы элемент [0][0] был равен единице, то мы могли бы объединить четыре квадрата размером 1, чтобы создать новый квадрат размером 2×2 с элементом [1][1] в качестве элемента в правом нижнем углу. Помните, что динамическое программирование – это разбиение более крупной проблемы на более мелкие проблемы.
Обратите внимание, как этот алгоритм обновляет матрицу на месте: для всех элементов, индекс которых равен 0 (значения первой строки и первого столбца) Эти элементы могут быть только нижним правым углом квадратов размером 1, поэтому мы не вводим условие if для этих элементов, мы просто добавляем их значение в “res”, которое равно либо 0, либо 1. для любого другого элемента со значением 1 существует потенциал для этого элемента чтобы быть нижним правым углом большего квадрата, поэтому мы выполняем этот процесс для проверки: мы получаем минимальное значение для левого, верхнего левого и верхнего элементов из нашего текущего элемента, который мы обрабатываем. Более формально мы получим минимальное значение для квадратов, для которых элементы A[i – 1][j], A[i][j – 1] и A[i – 1][j – 1] образуют значения правого угла. Как только мы получим минимальное значение, это означает, что каждый из этих меньших квадратов может быть объединен с текущим элементом, который мы обрабатываем, чтобы сформировать новый квадрат, больший, чем меньшие квадраты, на 1 строку и 1 столбец.
Давайте посмотрим на процесс объединения, здесь у нас есть матрица всех единиц:
Посмотрите на элемент A[2][[2], очевидно, что максимальный квадрат, который этот элемент образует в правом нижнем углу, имеет размер 3×3. Как мы можем рассчитать это, когда достигнем этого элемента? Мы должны будем увидеть ранее рассчитанные значения в левом, верхнем левом и верхнем элементах. Здесь у меня есть заштрихованный квадрат 2×2, в правом нижнем углу которого находится элемент A[1] [2]. К тому времени, когда мы обрабатываем элемент A[2][2], элемент A[1][2] будет иметь значение максимального квадрата, который имеет [1][2] в качестве нижнего правого угла (который равен 2). Мы все еще обрабатываем тот же элемент, но теперь мы смотрим на другой соседний элемент, элемент [2][1], который также является нижним правым углом квадрата размером 2.
Здесь мы смотрим на нашего последнего соседа в позиции [1] [1], который также является частью квадрата 2×2. Все соседние элементы являются частями квадратов размером 2×2. Поэтому мы можем безопасно “объединить” эти квадраты 2×2, чтобы сформировать больший квадрат размером 3×3 с элементом [2] [2] в качестве элемента в правом нижнем углу.
Я надеюсь, что это сделало интуицию, лежащую в основе решения для динамического программирования, более понятной. Продолжайте практиковать проблемы и удачи!
Оригинал: “https://dev.to/fatmasherif98/leetcode-may-challenge-count-square-submatrices-with-all-ones-1cap”