Автор оригинала: Rishabh Daal.
Проблемы динамического программирования широко задаются в технических интервью, особенно при приеме на работу новичков. Эти проблемы, как правило, не требуют предварительного знания какого-либо конкретного алгоритма, и решения, как правило, легко кодируются, но труднодоступны. В этом посте мы рассмотрим, что такое “Динамическое программирование”, а затем обсудим некоторые проблемы динамического программирования, заданные в технических интервью таких технологических гигантов, как Google, Facebook, Amazon, Microsoft.
Динамическое программирование разбивает проблему на более мелкие подзадачи и сохраняет результаты этих подзадач, чтобы гарантировать, что каждая подзадача будет решена только один раз.
Что такое подзадачи Подзадачи-это уменьшенные версии исходной проблемы, если они сформулированы правильно, подзадачи строятся друг на друге, чтобы получить решение исходной проблемы. Давайте разберемся в этом с помощью примера Фибоначчи, допустим, теперь нам нужно найти 5-е число Фибоначчи, которое мы знаем.
Шаг 1.
f i b ( 5 ) = f i b ( 4 ) + f i b ( 3 ) фвб(5)(4) + фвб(3) f i b ( 5 ) = f i b ( 4 ) + f i b ( 3 )
Здесь fib(4) и fib(3) являются подзадачей к исходной задаче fib(5).
Шаг 2.
f i b ( 4 ) = f i b ( 3 ) + f i b ( 2 ) фвб(4)(3) + фвб(2) f i b ( 4 ) = f i b ( 3 ) + f i b ( 2 )
точно так же мы можем сформировать дерево, подобное этому. здесь вы можете видеть, что в процессе оценки fib(5) мы вычисляем fib(3) дважды, который, в свою очередь, вычисляет fib(2) трижды. Поэтому вместо того, чтобы вычислять fib(2) и fib(3) снова и снова, мы можем просто хранить их значение, когда мы вычисляли их в первый раз, и использовать их всякий раз, когда это понадобится в будущем. Теперь давайте напишем два решения для этого. Во-первых, простое решение с перекрывающимися подзадачами
def fib(n):
if(n <= 1 ):
return n
return fib(n-1) + fib(n-2)
Теперь давайте взглянем на решение для динамического программирования.
def fib(n):
store = []*(n+1)
store[0], store[1] = 1, 1
for in range(2,n+1):
store[i] = store[i-1] + store[i-2]
return store[n]
Теперь давайте посмотрим на сравнение времени, затраченного обоими кодами.
Подзадачи против перекрывающихся подзадач Подзадачи нужны снова и снова, они классифицируются как перекрывающиеся подзадачи. Хранение значений перекрывающихся подзадач оптимизирует решение, поскольку мы избегаем вычислений, необходимых для вычисления одной и той же подзадачи снова и снова. Как и в приведенном выше примере чисел Фибоначчи, подзадача fib(2) вычисляется 3 раза. Мы ничего не получаем, сохраняя результаты для неперекрывающихся подзадач, как в binary_search, есть смысл хранить результаты для под-массива, так как эта подзадача больше не будет использоваться.
Динамическое программирование используется для решения задач, которые имеют перекрывающиеся подзадачи.
Пример задачи Для дальнейшего чтения мы будем использовать эту задачу в качестве ссылки. Учитывая a MxN board, нам нужно найти количество способов добраться до ячейки B , начиная с ячейки A . Из ячейки (x,y) вы можете перейти в ячейку (x+1,y) или ячейку (x,y+1) ( если вы не пересекаете границы) . Например, доска 2×2 существует 6 способов.
Определите проблему динамического программирования В большинстве случаев проблемы динамического программирования делятся на две категории.
1. Задача оптимизации. 2. Комбинаторная задача. Еще один намек, который вы увидите, заключается в том, что решение исходной проблемы зависит от более мелких подзадач, поскольку эти подзадачи будут перекрываться подзадачами.
В нашем примере задача сетки является комбинаторной задачей. давайте рассмотрим пример задачи для перекрывающейся подзадачи. давайте возьмем пример сетки 3х3. Давайте определим функцию
функция(x,y) способов достижения ячейки (x,y).
Теперь для ячейки (x,y) мы знаем, что единственный способ достичь (x,y)-это из ячейки (x-1,y) или ячейки (x,y-1), следовательно, мы можем сказать, что количество способов достичь ячейки (x,y)-это сумма количества способов достичь ячейки (x,y-1) и (x-1,y)
func (Х, У) (Х,У-1) + func(х-1,у) func(х,у-1) = func(х-1,у-1) + func (х,у-1) (х-2,у) + func (х-1, у-1)
мы ясно видим,что функция подзадачи(x-1, y-1) повторяется, мы будем обнаруживать все больше и больше повторяющихся терминов, если будем продолжать в том же духе. Теперь, поскольку у нашей проблемы есть перекрывающиеся подзадачи, следовательно, она является кандидатом на проблему динамического программирования.
Решение задачи динамического программирования
DP “Состояние”-это минимальная информация, которая может однозначно определить подзадачу для исходной задачи. Как и в нашей задаче,пара (x, y) является состоянием Dp, поскольку она однозначно определяет подзадачу, которую ни один из (x) или (y) не может.
Каждая задача динамического программирования имеет схему, которой нужно следовать:
1.Разбейте на оптимальные подзадачи и найдите состояние Dp. 2.Выразите проблему в терминах более мелких подзадач. 3.Вычислите оптимальное решение снизу вверх. 4.Постройте оптимальное решение на основе вычисленной информации.
Сверху вниз с мемуаризацией: взято из здесь Вы предполагаете, что уже вычислили все подзадачи. Вы понятия не имеете об оптимальном порядке оценки. Обычно вы выполняете рекурсивный вызов (или какой-либо итеративный эквивалент) из корня и либо надеетесь, что приблизитесь к оптимальному порядку оценки, либо у вас есть доказательство того, что вы получите оптимальный порядок оценки. Вы гарантируете, что рекурсивный вызов никогда не пересчитает подзадачу, потому что вы кэшируете результаты, и, таким образом, дубликаты поддеревьев не пересчитываются.
def count(x, y, store):
# check if subproblem (x,y) is already calculated
if( (x,y) in store):
return store[(x,y)]
# if outside of the board
if(x < 0 or y < 0 ):
return 0
# Base case of starting cell
if( x == 0 and y == 0 ):
return 1
# ans in terms of subproblems
ans = count(x,y-1,store) + count(x-1,y,store)
# Store the result for future
store[(x,y)] = ans
return ans
Снизу вверх: Вы также можете думать об этом как об алгоритме “заполнения таблицы” (хотя обычно многомерная, эта “таблица” может иметь неевклидову геометрию в очень редких случаях*). Это похоже на запоминание, но более активное, и включает в себя один дополнительный шаг: вы должны заранее выбрать, в каком именно порядке вы будете выполнять свои вычисления (это не означает, что порядок должен быть статичным, но у вас гораздо больше гибкости, чем у запоминания).
int count(int m, int n)
{
int dp[m][n];
// fill first column
for (int i = 0; i < m; i++)
dp[i][0] = 1;
// fill first row
for (int j = 0; j < n; j++)
dp[0][j] = 1;
// dp transitions.
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
return dp[m-1][n-1];
}
Оставайтесь в курсе следующего поста, в котором мы решим проблемы динамического программирования, заданные в интервью Google.