Повысьте свои навыки проведения собеседований и станьте лучшим разработчиком, изучив основы динамического программирования.
Динамическое программирование — это подход к решению сложных задач, который включает в себя разбиение задачи на более простые задачи и их решение. Если бы вас попросили умножить 21 * 5, вы, вероятно, вместо этого умножили бы (20 * 5) и добавили (1 * 5). Вместо того, чтобы решать одну сложную проблему, вы разбили ее на три более простые задачи и решили их.
- 20 * 5 = 100
- 1 * 5 = 5
- 100 + 5 = 105
Как мы увидим, это не точно то же самое, что происходит в динамическом программировании, но оно иллюстрирует основную идею решения сложной проблемы путем разбиения ее на несколько более простых задач.
Проблема с раздачей монет
Одной из задач, наиболее часто используемых для объяснения динамического программирования, является проблема размена монет. Проблема заключается в следующем.
Вам дан целочисленный массив «coins», представляющий монеты разного номинала, и целочисленное значение «amount», представляющее общую сумму денег.
Верните наименьшее количество монет, которое вам нужно, чтобы составить эту сумму. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, верните -1.
Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Так, например, предположим, что мы работаем с обычными монетами США (пенни, пятаки, десять центов, четвертаки) и нам нужно вернуть сдачу в размере 87 центов. В этом сценарии нам будет дано два входа:
amount = 87 coins = [ 1, 5, 10, 25 ]
Наименьшее количество монет, которое мы можем использовать для возврата 87 центов сдачи, составляет 6 монет: 3 четверти, 1 цент и 2 пенса. Итак, наша функция должна вернуть 6.
Сначала давайте подумаем, как бы мы подошли к этому без использования динамического программирования. Самое простое решение — метод грубой силы. Просто определите все возможные комбинации монет, которые составляют 87, а затем верните размер наименьшей коллекции. Это работает, но крайне неэффективно, особенно для больших задач.
Другой подход заключается в использовании жадного алгоритма. Жадный алгоритм — это алгоритм, который делает лучший выбор на каждом шаге, называемый локально оптимальным выбором. В этом случае это означало бы всегда выбирать самую большую монету, которая подходит. Давайте посмотрим, как это будет работать здесь, шаг за шагом.
- Осталось: 87. Выберите: четверть (25).
- Осталось: 62. Выберите: четверть (25).
- Осталось: 37. Выберите: четверть (25).
- Осталось: 12. Выберите: десять центов (10).
- Осталось: 2. Выберите: пенни (1).
- Осталось: 1. Выбрать: копейка (1).
Решение: 6
С помощью жадного алгоритма мы быстро обнаруживаем, что наименьшее количество требуемых монет составляет 6 монет (3 четверти, 1 десятицентовик и 2 пенни).
Жадное решение отлично работает для этого конкретного примера. На самом деле это работает для любого примера с использованием монет США из-за специфического номинала, используемого монетами США. Но бывают ситуации, когда он не может найти правильное решение проблемы размена монет в более общем плане. Рассмотрим следующую проблему.
amount = 20 coins = [ 3, 8, 11 ]
Жадный алгоритм предпримет следующую попытку.
- Осталось: 20. Выберите: 11.
- Осталось: 9. Выберите: 8.
- Осталось: 1. Нет правильного выбора.
Решение: -1 (неразрешимо)
Но это неправильно. После первого выбора из 11 у нас осталось 9. Забегая вперед, мы видим, что это можно выполнить, выбрав 3 три раза. Но наш жадный алгоритм этого не знает. Он разработан, чтобы сделать локально оптимальный выбор — выбрать самый высокий номинал, который в настоящее время доступен. В этом случае, поскольку поместится 8 (из оставшихся 9), выбирается 8. Что нам нужно, так это алгоритм, который может заглядывать вперед и видеть, что, хотя 8 является локально оптимальным выбором, в долгосрочной перспективе это не оптимальный выбор. Это именно то, что делает динамическое программирование. Как поясняется в одном из определений динамического программирования, динамическое программирование разработано таким образом, что оптимальное решение общей проблемы зависит от оптимального решения ее подзадач.
Ключом к динамическому программированию является определение подзадачи, которая придает основной проблеме «свойство оптимальной подструктуры». Это всего лишь формальный способ сказать, что ключ состоит в том, чтобы определить подзадачу, которая позволит нам решить основную проблему, просто решая подзадачу повторно.
В качестве простой иллюстрации предположим, что мы живем в мире, где сложение любых двух чисел больше 1 просто слишком сложно, и нам дали невыполнимую задачу решить для 3 + 2. Как оказалось, нам повезло. ! Наша задача обладает свойством оптимальной подструктуры. Мы знаем, что 2 — это просто 1 + 1. Поэтому мы можем просто решить нашу задачу.
3 + (1 + 1)
И мы знаем, что 3 равно 2 + 1, поэтому мы можем еще упростить до
(2 + 1) + (1 + 1)
Мы уже решили подзадачу для 2. Это 1 + 1. Таким образом, нашу исходную задачу можно переписать только как повторное решение нашей подзадачи.
1 + 1 + 1 + 1 + 1
Теперь это проблема, которую мы можем решить. (Любой математик, читающий это, будет недоволен моей иллюстрацией, и это правильно. Не думайте об этом слишком много. Это не математическое доказательство, а просто иллюстрация.)
Возвращаясь к нашей проблеме размена монет, наша задача состоит в том, чтобы определить подзадачу («1 + 1»), которую мы можем решать многократно, чтобы решить нашу основную проблему. Это сложная задача, но на самом деле она намного проще, чем кажется. На самом деле вы уже знаете ответ, просто не осознаете его.
Вот как мы к этому подойдем. Если данная проблема размена монет разрешима, то в какой-то момент мы доберемся до финальной монеты, номинал которой в точности равен оставшейся сумме. Итак, представьте, что мы используем стандартные монеты США и у нас осталось пять центов для сдачи. Пятак точно равен этой сумме, поэтому нашей последней монетой будет этот пятак. Это означает, что общее количество возвращенных монет будет равняться количеству монет, которые мы ранее вернули (количество монет, которое нам нужно, чтобы осталось всего 5 центов) плюс еще один: наш окончательный никель.
Мы можем представить то, что только что сказали, с помощью следующего формального описания.
F(a) = F(a - c) + 1
где
- F = наша функция для определения количества монет
- a = сумма возврата сдачи за
- c = номинал последней монеты, которую мы вернем
Это будет выглядеть так: «Минимальное количество монет, необходимое для возврата сдачи на сумму a, равно единице плюс минимальное количество монет, необходимое для возврата сдачи на a минус c, где c — это последняя монета, используемая для возврата сдачи».
Итак, применяя это к нашему примеру с никелем, давайте предположим, что сумма, на которую мы возвращаем сдачу, составляет 40 центов. Это означает, что a = 40. А поскольку мы сказали, что пятак будет последней монетой, которую мы вернем, это означает, что c = 5. Таким образом, подставляя эти значения вместо a и c, мы получаем
F(40) = F(40 - 5) + 1
что упрощает до
F(40) = F(35) + 1
Другими словами, количество монет, необходимое для получения сдачи в 40 центов, равно количеству монет, необходимому для получения сдачи в 35 центов, плюс еще одна монета (наш последний пятицентовик).
Вот ключевой ход — теперь мы решим эту же подзадачу (назовем ее «подзадача последней монеты») для 35.
F(35) = F(35 - c) + 1
Здесь мы будем использовать десятицентовик в качестве последнего достоинства монеты (через минуту мы рассмотрим, как делается этот выбор, а пока давайте просто предположим, что это десятицентовик). Таким образом, подставляя десятицентовую монету (10) вместо с, мы получаем
F(35) = F(35 - 10) + 1
что упрощает до
F(35) = F(25) + 1
Таким образом, количество монет, необходимое для возврата сдачи на 35 центов, равно количеству монет, необходимому для возврата сдачи на 25 центов, плюс еще одна монета (использованный нами десятицентовик). Помните, что наше предыдущее уравнение было
F(40) = F(35) + 1
Мы можем заменить наше вновь найденное F(35), и мы получим
F(40) = (F(25) + 1) + 1
or
F(40) = F(25) + 2
Таким образом, количество монет, необходимое для возврата сдачи на 40 центов, равно количеству монет, необходимому для возврата сдачи на 25 центов, плюс еще 2 монеты (пятак и пятицентовик, которые мы использовали в двух предыдущих подзадачах). Отсюда легко увидеть, что наше решение проблемы равно 3. Повторно решая нашу последнюю подзадачу о монетах, мы решили нашу исходную проблему.
Теперь последнее, что нам нужно знать, это как определить, какая монета должна быть последней монетой для данной подзадачи конечной монеты. По сути, мы будем повторять методом проб и ошибок, чтобы определить, какая монета обеспечивает оптимальное решение данной подзадачи. Выполнение этого для каждой подзадачи даст нам оптимальное решение нашей основной проблемы.
Мы можем выбрать один из двух подходов к кодированию: подход «сверху вниз» или подход «снизу вверх». В этой статье мы рассмотрим нисходящий подход.
Нисходящий (рекурсивный) подход
В нисходящем подходе мы начнем со стартовой суммы и рекурсивно попытаемся решить нашу подзадачу, используя каждый возможный номинал монеты в качестве «конечной монеты» в нашей подзадаче. Таким образом, используя приведенный выше пример со стандартными монетами США, наша проблема заключается в следующем.
amount = 40 coins = [ 1, 5, 10, 25 ]
и мы бы представили нашу подзадачу как
min_coins(40) = min_coins(40 — c) + 1
и решить для каждого возможного значения c (using standard US coins 1, 5, 10, 25) и использовать оптимальный результат (т.е. наименьшее необходимое количество монет).
Так что мы бы проверили
min_coins(40 — 25) + 1min_coins(40 — 10) + 1min_coins(40 — 5) + 1min_coins(40 — 1) + 1
и для каждой из этих возможных монет мы рекурсивно проверяем эти подзадачи. Так
min_coins(40 — 25) + 1
упрощается до
min_coins(15) + 1
а затем решаем эту подзадачу для каждой возможной монеты
min_coins(15 — 25) + 1 => -1min_coins(15 — 10) + 1min_coins(15 — 5) + 1min_coins(15 — 1) + 1
Обратите внимание, что наша первая попытка в этом случае дает -1, что означает неразрешимое решение. Это показывает, что наш алгоритм динамического программирования определил, что когда мы возвращаем сдачу на 40 центов, мы не можем начать с выбора двух четвертаков.
Последнее понятие, которое нам нужно понять, прежде чем мы рассмотрим какой-либо код, — это запоминание. Мемоизация просто относится к кэшированию результатов дорогостоящих вызовов функций, поэтому нам не нужно снова вызывать функцию. Так, например, как только мы подсчитали минимальное количество монет, необходимое для внесения сдачи на 11 центов, мы кэшируем этот результат и используем его для всех будущих вызовов, чтобы нам не приходилось каждый раз пересчитывать его.
Хорошо, давайте посмотрим на код. Чтобы сделать барьер как можно ниже, я предоставлю решение на Javascript, Python, Kotlin и Swift. Не стесняйтесь использовать тот язык, который вам наиболее удобен, так как все четыре фрагмента содержат один и тот же алгоритм. После приведенного ниже кода мы проведем оставшуюся часть статьи, шаг за шагом просматривая код.
Javascript
питон
Котлин
Быстрый
Давайте пройдемся по коду. (Заранее извиняюсь перед читателями Python за обращение к именам переменных с использованием верблюжьего регистра, но все остальные 3 языка используют верблюжий регистр). У нас есть две функции, обе названы coinChange. Первый принимает два наших входа coins и amount в качестве параметров. Вторая функция добавляет дополнительный параметр с именем solutions. Этот параметр является нашей таблицей запоминания. Когда мы найдем решение подзадачи на сумму, например, 8, мы сохраним это в 8-м индексе массива таблицы мемоизации. В нашей исходной функции мы создадим это как пустой массив размера, достаточно большой, чтобы содержать решения для всех возможных подзадач.
Вторая функция coinChange будет служить нашей рекурсивной функцией. Сначала она вызывается функцией first coinChange, а затем продолжает вызывать себя, используя оставшуюся сумму для следующей подзадачи при каждом вызове. По этой причине второму параметру присвоено имя amountRemaining, а не amount, как мы сделали в первой функции. Итак, давайте пройдемся по рекурсивной функции.
Первые две строки охватывают базовые условия для рекурсивной функции. Если наша оставшаяся сумма меньше 0, то мы достигли невозможного решения и возвращаем -1, как указано в инструкциях к задаче. Если оставшаяся сумма ровно 0, мы возвращаем 0, поскольку для внесения сдачи на сумму 0 требуется 0 монет.
Следующий шаг использует нашу таблицу запоминания solutions. Прежде чем мы вычислим, как внести сдачу на amountRemaining, нам нужно проверить, не рассчитали ли мы уже, как лучше всего произвести сдачу на amountRemaining (которая будет храниться в solutions по индексу amountRemaining — 1). Если это так, верните кэшированное значение, которое мы уже вычислили.
Если мы пройдем эти три шага, то у нас будет действительное amountRemaining, для которого мы еще не определили оптимальное решение. Итак, теперь нам нужно определить оптимальное решение для amountRemaining. Мы сделаем это, исследуя, что произойдет, если мы будем использовать каждую из имеющихся у нас монет. Вот тут и возникает рекурсия.
Предположим, мы пытаемся внести сдачу на 72 цента, а в нашем гипотетическом сценарии у нас осталось 47 центов. Мы определим оптимальное решение для внесения сдачи на 47 центов, рекурсивно вызвав нашу функцию coinChange для каждого возможного достоинства монеты. По сути, мы говорим: «Предположим, в этот момент мы выбираем следующий квартал. Сколько монет потребуется, чтобы произвести сдачу? Что, если бы вместо этого мы выбрали десять центов? А никель? Как насчет копейки?
Ключевыми шагами являются следующие (синтаксис может немного отличаться в зависимости от вашего языка)
solutionUsingThisCoin = coinChange(coins, amountRemaining - coin, solutions)
и этот
if solutionUsingThisCoin >= 0 && solutionUsingThisCoin < optimalSolution {
optimalSolution = solutionUsingThisCoin + 1
}
Первая строка рекурсивно вызывает coinChange, чтобы определить наилучшее возможное решение подзадачи, если мы используем монету coin дальше. Вызывая это в цикле для каждой монеты и беря наименьший результат, мы вычисляем наилучшее возможное решение этой подзадачи независимо от того, какую монету мы выбираем. Теперь мы будем знать, например, что наилучшее возможное решение подзадачи amountRemaining = 47 равно 5 (это 1 четверть, 2 десятицентовика и 2 пенни, но для нашей реальной задачи нам все равно, какие именно монеты). ). Мы обновляем optimalSolution на solutionUsingThisCoin + 1, где 1 представляет саму тестовую монету. Это кодовая реализация подзадачи, которую мы формально описали выше как F(a) = F(a — c) + 1. И, наконец, мы кэшируем наше вновь найденное решение подзадачи (или -1, если это невозможно) в нашей таблице мемоизации и возвращаем значение.
Заключение
Динамическое программирование используется в ряде задач, включая задачу о размене монет, задачу о рюкзаке и нахождение последовательности Фибоначчи. Это тип вопросов, которые вы можете услышать на собеседовании, поэтому большинству разработчиков программного обеспечения стоит понимать динамическое программирование только по этой причине. Но даже если вы не ожидаете, что ответите на них в интервью, разработка программного обеспечения — это область, в которой мы всегда стремимся углубить свое понимание и найти новые способы решения проблемы. Динамическое программирование — отличный пример этого, и я надеюсь, что вы нашли его полезным.
