Нравится вам это или нет, но вопросы Leetcode являются частью каждого собеседования по программированию. Вопросы Leetcode можно разделить на множество категорий: динамическое программирование, жадность, манипулирование битами, массивы и т. д.
Я старший инженер-программист-самоучка, который решил сделать перерыв и получить степень в университете. Практикуя Leetcode для интервью, я был поражен тем, как элегантно решают сложные вопросы лучшие lee-кодеры.
Во время моего класса алгоритмов в этом году я собрал воедино подход к решению вопросов динамического программирования. Часть основана на проверенных академических знаниях, а часть — на моем опыте проведения собеседований.
Метод
Метод состоит всего из трех шагов:
- Определите подзадачи
- Запишите формулу рекурсии.
- Табулирование/запоминание
Подзадачи
Если вы здесь, то наверняка знаете, что такое динамическое программирование. Формально это относится к упрощению сложной проблемы путем ее рекурсивного разбиения на более простые подзадачи.
Подзадачи строятся друг на друге, чтобы получить решение проблемы. Проблема может зависеть от одной подзадачи, или вам может потребоваться решить половину набора данных, затем вторую половину и объединить результат.
Формула рекурсии
На этом шаге мы пишем конкретную формулу для вычисления задачи на основе ее подзадач. Вы также можете знать это как формулу перехода. Мы должны помнить об условиях остановки.
Табуляция против мемоизации
Этот шаг связан с самой реализацией. Решить можно либо сверху вниз с мемоизацией, либо снизу вверх с помощью табуляции. Табулирование предпочтительнее.
Мы должны рассмотреть, как извлечь решение. Можем ли мы извлечь его непосредственно из одной из ячеек или нам придется перебирать таблицу и обрабатывать результаты?
Давайте рассмотрим задачу средней сложности из leetcode.
Максимальная площадь
Учитывая бинарную матрицу m x n, заполненную 0 и 1, найдите самый большой квадрат, содержащий только 1, и верните его площадь.
Подзадачи: для каждой ячейки (i,j) найдите самый большой квадрат (длину стороны), чтобы (i,j) был левым верхним углом квадрата.
Формула рекурсии. Чтобы найти самый большой квадрат, начинающийся в текущей ячейке (i,j), нам нужно знать количество последовательных 1 справа от (i,j) , количество последовательных 1 под (i,j) и размер самого большого квадрата в (i+1, j+1) . Затем нам нужно было бы взять как минимум три, чтобы получить фактический размер квадрата.
На первый взгляд, мы не знаем количество последовательных 1 ниже и справа от (i,j), так как мы вычисляем квадратный размер каждой ячейки. Обратите внимание, что можно вывести количество последовательных 1, используя размер квадрата, расположенный в (i+1,j) и (i,j+1) для строк и столбцов соответственно.
Не забывайте обрабатывать записи с 0 и базовым регистром. Следовательно, мы можем написать следующую формулу:
Как мы приходим к окончательному ответу, не проходя через неоптимизированные решения, такие как грубая сила или менее оптимизированное решение DP? Определив, что мы ищем на этапе подзадач, становится ясно, что нам нужно рассчитать; на этом шаге нам нужно только найти, как его вычислить.
Табулирование. Каждая подзадача определяется (i,j) координатами ячейки. Это два параметра, поэтому нам нужна 2D-таблица размером m x n . Каждая ячейка в таблице должна содержать наибольший размер квадрата соответствующей записи в матрице.
Мы заполним таблицу с (i,j) = (n-1,m-1) и будем двигаться в обратном направлении по формуле. Неважно, перебираем ли мы сначала строки или столбцы.
Чтобы вернуть ответ, мы могли либо перебрать всю доску заново, либо, что еще лучше, сохранить максимальный размер и вернуть его после итерации. Этот алгоритм O(m*n).
class Solution:
def maximalSquare(self, mat: List[List[str]]) -> int:
if not mat:
return 0
m = len(mat)
n = len(mat[0])
maxLength = 0
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if mat[i][j] == '1':
dp[i][j] = 1 + min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
maxLength = max(maxLength, dp[i][j])
return maxLength**2
