Что означает +1 в рекуррентном соотношении для задачи смены монет (подход динамического программирования)?

Question

Я видел проблему со сменой монет.В общем случае, вводом является n (возвращаемое изменение) и доступные номиналы (значения монет в центах), v ₁ 2 1 <... <v <sub>k ;цель состоит в том, чтобы внести изменение в n центов с минимальным количеством монет.

Я читал этот pdf из Колумбийского университета, но я не получаюпочему на слайде № 6 у нас есть + 1 в рекуррентном отношении:

Представляет ли мы монеты, которые мыВы уже использовали?

Answer 1

C[p] указывает минимальное количество монет для построения номинала p из доступного массива монет d.

Таким образом, чтобы создать такую ​​сумму, вы должны выбрать монеты d[i] такие, что d[i]<p.

Давайте предположим, что вы выбрали монету d [i] из d. А это значит, что теперь у вас есть монета.

Теперь, чтобы сделать сумму p, соберите больше монет на сумму p-d[i].

Но у вас уже были min_coins, необходимые для получения суммы p-d[i] в C[p-d[i]].

Это означает, что одно возможное количество монет для получения суммы p равно 1+C[p-d[i]].

Но может быть несколько конфессий, где возможно d[i]<p, тогда вам нужно выбрать тот, который приведет вас к минимуму, и это именно то, что делает ваша функция.

Таким образом, вы можете понять, что +1 функционирует как первая монета, которую мы рассматриваем для получения суммы p.

Answer 2

Предположим, мои деноминации выглядят так: d = [1, 5, 10, 25]. Давайте также предположим, что n, возвращаемое изменение равно 26. Это означает, что:

C[26] = min{C[26 - d[i]] + 1}

, который может быть выражен как:

C[26] = min{C[25], C[21], C[16], C[1]} + 1.

Здесь «+1» - это просто монета, которую нужно добавить к одной из ранее решенных подзадач (например, C [25], C [21]), чтобы получить C [26].

Если мы рассмотрим еще более простой пример, например, n = 6 с теми же номиналами, мы знаем, что повторение будет:

C[6] = min{C[6 - d[i]]} + 1

или

C[6] = min{C[5], C[1]} + 1

Мы знаем, что C [5] равно 1 (потому что минимальный способ сделать 5 центов с номиналом 5 в миксе равен 1), и аналогично C [1] = 1. Минимальный здесь только 1, поэтому 1 + 1 = 2, а минимальное количество монет, необходимое для получения 6 центов, составляет 2 монеты.