Динамическое программирование: примеры, общие проблемы и решения

Нет сомнений в том, что задачи динамического программирования могут быть очень пугающими на собеседовании по кодированию. Даже если вы знаете, что проблему необходимо решить с помощью метода динамического программирования, сложно найти рабочее решение в ограниченные сроки.

Лучший способ научиться решать задачи динамического программирования - решить как можно больше из них. Хотя вам не обязательно запоминать решение каждой проблемы, неплохо иметь представление о том, как его реализовать.

Что такое динамическое программирование?

Проще говоря, динамическое программирование - это метод оптимизации рекурсивных алгоритмов, большинство из которых используются для решения вычислительных или математических задач.

Вы также можете назвать это алгоритмическим методом решения проблемы оптимизации, разбив ее на более простые подзадачи. Ключевой принцип, на котором основано динамическое программирование, заключается в том, что оптимальное решение проблемы зависит от решений ее подзадач.

Везде, где мы видим рекурсивное решение, которое повторяет вызовы одних и тех же входных данных, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже.

Динамически запрограммированные решения имеют полиномиальную сложность, которая обеспечивает гораздо более быстрое время выполнения, чем другие методы, такие как рекурсия или обратное отслеживание. В большинстве случаев динамическое программирование сокращает временные сложности, также известные как большой-O, от экспоненты к полиномиальной.

Что такое нотация Big-O?

Ваш код должен быть эффективным, но как показать, насколько он эффективен? С Big-O!

Теперь, когда у вас есть хорошее представление о том, что такое динамическое программирование, пора проверить несколько распространенных проблем и их решения.

Задачи динамического программирования

1. Проблема с рюкзаком

Постановка задачи

Учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, который нужно включить в коллекцию, чтобы общий вес не превышал заданный предел, а общее значение не превышало возможный.

Вам даны два целочисленных массива значения [0..n-1] и веса [0..n-1] которые представляют значения и веса, связанные с n элементами соответственно. Также дано целое число W что представляет собой вместимость ранца.

Здесь мы решаем задачу о рюкзаке 0/1, что означает, что мы можем либо добавить элемент, либо исключить его.

Алгоритм

• Создайте двумерный массив с п + 1 ряды и w + 1 столбцы. Номер строки п обозначает набор элементов от 1 до я, и номер столбца ш обозначает максимальную грузоподъемность сумки.
• Числовое значение в [i] [j] обозначает общую стоимость предметов до я в сумке, рассчитанной на максимальный вес j.
• По каждой координате [i] [j] в массиве выберите максимальное значение, которое мы можем получить без пункт я, или максимальное значение, которое мы можем получить с пункт яв зависимости от того, что больше.
• Максимальное значение, которое можно получить, включив элемент i, представляет собой сумму элемента я собственно и максимальное значение, которое можно получить с оставшейся вместимостью ранца.
• Выполняйте этот шаг, пока не найдете максимальное значение для W^th ряд.

Код

def FindMax (W, n, значения, веса):
MaxVals = [[0 для x в диапазоне (W + 1)] для x в диапазоне (n + 1)]
для i в диапазоне (n + 1):
для w в диапазоне (W + 1):
если i == 0 или w == 0:
MaxVals [i] [w] = 0
elif weights [i-1] <= w:
MaxVals [i] [w] = max (значения [i-1]
+ MaxVals [i-1] [w-weights [i-1]], 
MaxVals [i-1] [w])
еще:
MaxVals [i] [w] = MaxVals [i-1] [w]
return MaxVals [n] [W]

2. Проблема смены монеты

Постановка задачи

Предположим, вам дан массив чисел, представляющих стоимость каждой монеты. Учитывая определенную сумму, найдите минимальное количество монет, необходимых для ее получения.

Алгоритм

• Инициализировать массив размера п + 1, где n - количество. Инициализировать значение каждого индекса я в массиве быть равным сумме. Это означает максимальное количество монет (с использованием монет достоинством 1), необходимое для пополнения этой суммы.
• Поскольку для 0 нет обозначения, инициализируйте базовый случай, когда массив [0] = 0.
• Для любого другого индекса я, мы сравниваем в нем значение (которое изначально установлено на п + 1) со значением массив [i-k] +1, куда k меньше чем я. По сути, это проверяет весь массив до i-1, чтобы найти минимально возможное количество монет, которое мы можем использовать.
• Если значение при любом массив [i-k] + 1 меньше существующего значения в массив [я]замените значение на массив [я] с одним в массив [i-k] +1.

Код

def coin_change (d, сумма, k):
числа = [0] * (сумма + 1)
для j в диапазоне (1, сумма + 1):
минимум = сумма
для i в диапазоне (1, k + 1):
если (j> = d [i]):
минимум = минимум (минимум, 1 + числа [j-d [i]])
числа [j] = минимум
вернуть числа [сумма]

3. Фибоначчи

Постановка задачи

Ряд Фибоначчи - это последовательность целых чисел, где следующее целое число в ряду является суммой двух предыдущих.

Он определяется следующим рекурсивным отношением: F (0) = 0, F (n) = F (n-1) + F (n-2), куда F (п) затем^th срок. В этой задаче мы должны сгенерировать все числа в последовательности Фибоначчи до заданного n^th срок.

Алгоритм

• Во-первых, используйте рекурсивный подход для реализации данного рекуррентного отношения.
• Рекурсивное решение этой проблемы влечет за собой разрушение F (п) в F (n-1) + F (n-2), а затем вызов функции с F (п-1) и Ж (п + 2) как параметры. Мы делаем это до тех пор, пока не появятся базовые случаи, когда п = 0, или же п = 1 достигнуты.
• Теперь мы используем метод, называемый мемоизацией. Сохраните результаты всех вызовов функций в массиве. Это гарантирует, что для каждого n F (п) нужно рассчитывать только один раз.
• Для любых последующих вычислений его значение можно просто получить из массива за постоянное время.

Код

def fibonacci (n): 
fibNums = [0, 1] 
для i в диапазоне (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
вернуть fibNums [n] 

4. Самая длинная возрастающая подпоследовательность

Постановка задачи

Найдите длину самой длинной возрастающей подпоследовательности внутри данного массива. Самая длинная возрастающая подпоследовательность - это подпоследовательность в массиве чисел с возрастающим порядком. Числа в подпоследовательности должны быть уникальными и располагаться в порядке возрастания.

Кроме того, элементы последовательности не обязательно должны быть последовательными.

Алгоритм

• Начните с рекурсивного подхода, при котором вы вычисляете значение самой длинной возрастающей подпоследовательности каждый возможный подмассив от нулевого индекса до индекса i, где i меньше или равен размеру множество.
• Чтобы превратить этот метод в динамический, создайте массив для хранения значения для каждой подпоследовательности. Инициализируйте все значения этого массива равными 0.
• Каждый индекс я этого массива соответствует длине самой длинной возрастающей подпоследовательности для подмассива размера я.
• Теперь для каждого рекурсивного вызова findLIS (обр., n), проверить п^th индекс массива. Если это значение равно 0, вычислите значение, используя метод на первом шаге, и сохраните его в п^th индекс.
• Наконец, верните максимальное значение из массива. Это длина самой длинной возрастающей подпоследовательности заданного размера. п.

Код

def findLIS (myArray):
п = len (myArray)
lis = [0] * n
для i в диапазоне (1, n):
для j в диапазоне (0, i):
если myArray [i]> myArray [j] и lis [i] lis [i] = lis [j] +1
maxVal = 0
для i в диапазоне (n):
maxVal = max (maxVal, lis [i])
вернуть maxVal

Решения задач динамического программирования

Теперь, когда вы прошли через некоторые из самых популярных задач динамического программирования, пора попробовать реализовать решения самостоятельно. Если вы застряли, вы всегда можете вернуться и обратиться к разделу алгоритмов для каждой проблемы выше.

Учитывая, насколько популярны сегодня такие методы, как рекурсия и динамическое программирование, не помешает проверить некоторые популярные платформы, где вы можете изучить такие концепции и отточить свои навыки программирования. Хотя вы можете не сталкиваться с этими проблемами ежедневно, вы наверняка столкнетесь с ними на техническом собеседовании.

Естественно, знание общих проблем обязательно принесет дивиденды, когда вы пойдете на следующее собеседование. Так что открой свой любимая IDE, и приступим!

9 лучших каналов YouTube для обучения программированию

Готовы начать кодирование? Эти каналы YouTube - отличный способ начать разработку игр, приложений, Интернета и других направлений.

Об авторе