Базовый взгляд на динамическое программирование — проблема размена монет
Как и многие из вас, я борюсь с вопросами более высокого уровня, связанными с рекурсией и динамическим программированием. Моему мозгу трудно визуализировать эти концепции. Расшифровка чужого решения часто становится тарабарщиной, когда вы пытаетесь следовать этим вложенным циклам и динамическим массивам. Мне нужен какой-то способ увидеть эти проблемы в другом свете, чтобы понять их. Давайте посмотрим на «Проблему размена монет».
Имея список монет (например, 1 цент, 2 цента, 10 центов) и предполагая, что у вас есть бесконечное количество всех монет, сколькими способами вы можете получить целевую сумму из этих номиналов монет?
Так, например, если нашей целевой суммой было 12 центов, мы хотим выяснить, сколькими способами мы можем заработать 12 центов из монет стоимостью 1 цент, 2 цента и 10 центов.
- 1+1+1+1+1+1+1+1+1+1+1+1 = 12
- 1+1+1+1+1+1+1+1+1+1+2 = 12
- 1+1+1+1+1+1+1+1+2+2 = 12
- 1+1+1+1+1+1+2+2+2 = 12
- 1+1+1+1+2+2+2+2 = 12
- 1+1+2+2+2+2+2 = 12
- 2+2+2+2+2+2 = 12
- 1+1+10 = 12
- 2+10 = 12
Мы видим, что есть девять различных способов заработать 12 центов из этих конкретных монет. Теперь… как нам понять то, что мы здесь видим, и понять это.
Итак, для нашей задачи имеем:
N = 12
Индекс монет: [0,1, 2]
Монеты:[1,2,10]
Нам нужно придумать метод, который может использовать эти номиналы монет и сказать нам, сколькими способами мы можем получить сумму в 12 центов. Мы захотим разбить эту задачу на более мелкие подзадачи, но сохраним решения этих задач, чтобы нам не нужно было ничего вычислять дважды. Если монета больше, чем наша целевая сумма, нам не нужно об этом беспокоиться, и она не будет проверена, потому что мы собираемся проверить только нашу целевую сумму.
Давайте определим массив, который будет содержать решения наших подзадач. Мы назовем это нашим массивом путей, и каждый индекс представляет, сколько способов данный набор монет может сделать определенное значение до Nth. В нашей ситуации мы ищем до 12.
массив путей = [0,0,0,0,0,0,0,0,0,0,0,0,0]
Размер этого массива будет N+1, или до N-го значения (в нашем случае 12+1)
Причина наличия массива до N-го значения заключается в том, что мы можем определить количество способов, которыми монеты составляют сумму по индексуwaysArray. Если мы определяем, что монета больше, чем значение индекса нашего массива путей, то мы не можем использовать эту монету для определения перестановок, потому что монета больше этого значения.
N = 7
Индекс монет = [0,1,2]
монеты = [1,2,10]
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Прежде чем мы начнем, нам нужно задать нашему массиву путей предопределенное значение.
Мы установимwaysArray[ 0 ] = 1. Это потому, что это показывает, сколько способов мы можем сделать 0 из 0.
Мы пройдемся по всем монетам и сравним монету с индексомwaysArray, чтобы определить, сколько раз можно использовать монету, чтобы получить сумму по индексуwaysArray.
Начнем с нашей монеты в 1 цент.
N = 7
Индекс монет = [0,1,2]
монеты = [1,2,10]
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Сначала сравните значение монеты со значением индексаwaysArray и если оно меньше или равно. Затем посмотрите, сколько раз этот набор монет может составить эту сумму. Прямо сейчас мы просто смотрим на монету в 1 цент, поэтому мы начинаем:
Сколькими способами мы можем сделать 1 цент из 1-центовой монеты? Мы можем сделать это одним способом.
Сколькими способами мы можем сделать 2 цента из 1-центовой монеты? Мы можем сделать это одним способом.
Сколькими способами мы можем сделать 3 цента из 1-центовой монеты? Мы можем сделать это одним способом.
…и т.д…
Вы можете увидеть образец здесь для первой монеты. Имеет смысл, что для любого значения индекса будет только один способ заработать эту сумму, учитывая монеты в 1 цент.
Наше новое значение (которое является нашим текущим количеством способов заработать эту сумму с помощью этих монет) будет рассчитано с использованием:
массив путей[ j ] = массив путей[ j — массив монет[ i ]] + массив путей[ j ]
Первая итерация:
массив путей[ 1 ] = массив путей[ 1 — массив монет[ 0 ]] + массив путей[ 1 ]
массив путей [ 1 ] = массив путей [ 1–1 ] + массив путей [ 1 ]
массив путей [ 1 ] = 1 + 0
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Вторая итерация:
массив путей[ 2 ] = массив путей[ 2 — массив монет[ 0 ]] + массив путей[ 2 ]
массив путей [ 2 ] = массив путей [ 2–1 ] + массив путей [ 2 ]
массив путей [ 1 ] = 1 + 0
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
После того, как мы пройдемся по каждому индексу, наш массив путей будет выглядеть так:
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Если мы вернемся к нашим возможным решениям, мы увидим, что наше 1-е решение, 1+1+1+1+1+1+1+1+1+1+1+1 = 12, очень похоже на наши значения wayArray. …
Теперь мы пройдемся по нашему массиву путей с монетой в 2 цента, снова выполнив такое же сравнение. Если стоимость монеты меньше или равна значению индекса массива путей, то массив путей[j] = массив путей[j — монеты[i]] + массив путей[j].
Для индексов 0–1 мы даже не будем на них смотреть, потому что знаем, что невозможно сделать значения 0 центов, 1 цент из 2 центов.
Когда мы достигаем индекса 2, мы видим, что стоимость нашей монеты меньше или равна 2, поэтому мы делаем:
массив путей[ 2 ] = массив путей[ 2 — монеты[1]] + массив путей[ 2 ]
массив путей [ 2 ] = массив путей [ 2–2 ] + массив путей [ 2 ]
массив путей [ 2 ] = 1 + 1
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Что здесь происходит?
Мы хотим определить, сколько раз вторая монета (2 цента) входит во все значения, ведущие к N-й (12-й) монете. Мы используем все монеты, чтобы проверить наш предыдущий результат, и вместо того, чтобы пересчитывать какие-либо значения, просто добавляем их к нашему новому значению.
Мы только что подсчитали, что наш индекс вwaysArray[ 2 ] = 2
Мы знаем, что значение 2–2 равно 0, это и есть наше значение j — coins[ i ]. По сути, это различие, которое необходимо восполнить, чтобы получить значение 2. Мы видим, чтоwaysArray[ 0 ] = 1. Это говорит о том, что до сих пор мы вычислили 1 способ сделать 0. Итак, если есть один способ чтобы получить нулевое значение, то это количество способов плюс текущее количество способов — это новое обновленное общее количество способов получить сумму по индексу 2. Другой способ думать об этом — добавитьwaysArray[ 2 ] (что равно к 1 и показывает, сколько способов у нас есть в настоящее время, чтобы сделать значение 2). Это текущее значение — это только значение с использованием монеты «один», теперь мы должны добавить монету «два». Разница в стоимости индекса, стоимости монеты, дает нам сумму, которую нужно добавить. Снова 2–2 = 0, и мы знаем, что это один из способов сделать ноль из нуля, поэтому мы добавляем это к нашему текущему значению, чтобы получить обновленное значение.
массив путей[ 3 ] = массив путей[ 3 — монеты[1]] + массив путей[ 3 ]
массив путей [ 3 ] = массив путей [ 3–2 ] + массив путей [ 3 ]
массив путей [ 3 ] = 1 + 1
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
То же самое, что и раньше, у нас есть j — монет[ i ]
3–2 = 1
Опять же, 1 — это разница, которую необходимо компенсировать, чтобы получить значение 3.
массив путей[ 1 ] = 1
Это говорит о том, что мы рассчитали 1 способ сделать значение 1 с монетами, которые мы проверили до сих пор (1 цент, 2 цента).
Мы добавляем это к текущему количеству способов получить наше обновленное значение из общего количества способов получить значение по индексу 3.
массив путей[ 4 ] = массив путей[ 4 — монеты[1]] + массив путей[ 4 ]
массив путей [ 4 ] = массив путей [ 4–2 ] + массив путей [ 4 ]
массив путей [ 4 ] = 2 + 1
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1]
4 -2 = 2
2 — это разница, которую необходимо компенсировать, чтобы получить значение 4.
массив путей [ 2 ] = 2
До сих пор мы рассчитали 2 способа получить значение 2 с помощью монет (1 цент, 2 цента).
Наш текущий массивwaysArray[ 4 ] = 1, что означает, что мы рассчитали 1 способ сделать 4 на данный момент. Мы знаем, что это число плюс количество способов изменить ситуацию будет равняться общему количеству способов сделать нашу ценность. Мы рассчитали 2 способа сделать 2, что является нашей разницей, и добавили это к нашему текущему значению 1, что дает нам новое общее количество из 3 различных способов сделать 4, используя (1 цент, 2 цента).
массив путей[ 6 ] = массив путей[ 6 — монеты[1]] + массив путей[ 6 ]
массив путей [ 6 ] = массив путей [ 6–2 ] + массив путей [ 6 ]
массив путей [ 6 ] = 3 + 1
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 3, 4, 1, 1, 1, 1, 1, 1]
Когда мы закончим перебирать N с монетой в 2 цента, мы получим:
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7]
Вспомните наши комбинации… давайте посмотрим, что у нас есть…
- 1+1+1+1+1+1+1+1+1+1+1+1 = 12
- 1+1+1+1+1+1+1+1+1+1+2 = 12
- 1+1+1+1+1+1+1+1+2+2 = 12
- 1+1+1+1+1+1+2+2+2 = 12
- 1+1+1+1+2+2+2+2 = 12
- 1+1+2+2+2+2+2 = 12
- 2+2+2+2+2+2 = 12
7 комбинаций… и какое у нас значение вwaysArray[ 12 ]? Это 7.
Перейдем к последней монете 10:
Мы знаем, что поскольку номинал нашей монеты равен 10, то мы можем пропустить все индексы со значением ниже 10, потому что невозможно сделать 0 центов, 1 цент, 2 цента, 3 цента, 4 цента, 5 центов, 6 центов, 7 центов, 8 центов или 9 центов с 10 центами.
массив путей[ 10 ] = массив путей[ 10 — монеты[2]] + массив путей[ 10 ]
массив путей [ 10 ] = массив путей [ 10–10 ] + массив путей [ 10 ]
массив путей [ 10 ] = 1 + 6
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 7, 6, 7]
waysArray[10] был равен 6, то есть пока мы нашли 6 различных способов получить значение 10 с помощью монет (1 цент, 2 цента). Разница, которую мы пытаемся найти, это 10–10 = 0. Мы знаем, что есть один способ сделать 0 из 0, поэтому мы добавляемwaysArray[0] к нашим текущим путям, чтобы получить наши обновленные пути.
массив путей[ 11 ] = массив путей[ 11 — монеты[2]] + массив путей[ 11 ]
массив путей [ 11 ] = массив путей [ 11–10 ] + массив путей [ 11 ]
массив путей [ 10 ] = 1 + 6
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 7, 7, 7]
waysArray[ 11 ] был равен 6, то есть пока мы нашли 6 различных способов получить значение 11 с помощью монет (1 цент, 2 цента). Разница, которую мы пытаемся найти, это 11–10 = 1. Мы знаем, что есть 1 способ сделать 1, поэтому мы добавляемwaysArray[1] к нашим текущим путям, чтобы получить наши обновленные пути.
массив путей[ 12 ] = массив путей[ 12 — монеты[2]] + массив путей[ 12 ]
массив путей [ 12 ] = массив путей [ 12–10 ] + массив путей [ 12 ]
массив путей[ 12 ] = 2 + 7
Индекс путей Массив = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
массив путей = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 7, 7, 9]
waysArray[ 12 ] был равен 7, то есть пока мы нашли 7 различных способов получить значение 12 с помощью монет (1 цент, 2 цента). Разница, которую мы пытаемся найти, равна 12–10 = 2. Мы знаем, что до сих пор мы вычисляли 2 способа сделать из монет значение 2 (1 цент, 2 цента). Эти 2 способа — это то, что нам нужно добавить к нашему текущему количеству способов, чтобы получить сумму 12, чтобы получить наше обновленное количество способов, используя нашу новую монету (10 центов).
Оглядываясь назад, у нас было всего 9 комбинаций, которые мы могли составить. Мы можем увидеть наше значение вwaysArray[ 12 ] = 9. Это представляет собой общее количество способов, которыми мы можем использовать изменение (1 цент, 2 цента, 10 центов), чтобы получить значение 12 центов.
Это было много…
Теперь давайте посмотрим код.
