У меня есть проблемы с пониманием динамического программирования решения различных проблем, в частности, проблемы с монетой:

«При заданном значении N, если мы хотим внести изменения в N центов, и у нас есть бесконечный запас каждой из монет с достоинством S = {S1, S2, .., Sm}, сколько способов мы можем внести изменение? Порядок монет не имеет значения.

Например, для N = 4 и S = ​​{1,2,3} существует четыре решения: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. Таким образом, выходное значение должно быть 4. Для N = 10 и S = ​​{2, 5, 3, 6} существует пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Поэтому на выходе должно быть 5 ".

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

Эти проблемы выглядят очень похожими, но решения оченьразные.

Количество возможных способов внесения изменений: оптимальной основой для этого являетсяDP (m, n) = DP (m-1, n) + DP (m, n-Sm) где DP - количество решений для всех монет до m-й монеты и сумма = n.

Минимальное количество монет: оптимальная подструктура для этогоDP [i] = Min {DP [i-d1], DP [i-d2], ... DP [i-dn]} + 1 где i - общая сумма, а d1..dn - номинал каждой монеты.

Почему первый требует двухмерный массив, а второй - одномерный? Почему оптимальная подструктура для ряда способов внести изменения не "DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn]«где DP [i] - это количество способов, которыми я могу получить сумму монетами. Для меня это звучит логично, но дает неправильный ответ. Почему это второе измерение для монет необходимо в этой задаче, но не нужно в проблема минимального количества?

ССЫЛКИ НА ПРОБЛЕМЫ:

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

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