Estou tendo problemas com o entendimento de soluções de programação dinâmica para vários problemas, especificamente o problema de troca de moedas:

"Dado um valor N, se quisermos fazer alterações por N centavos, e temos um suprimento infinito de cada uma das moedas com valor de S = {S1, S2, .., Sm}, quantas maneiras podemos fazer a alteração? de moedas não importa.

Por exemplo, para N = 4 e S = {1,2,3}, existem quatro soluções: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. Portanto, a saída deve ser 4. Para N = 10 e S = {2, 5, 3, 6}, existem cinco soluções: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} e {5,5}. Portanto, a saída deve ser 5. "

Há outra variação desse problema em que a solução é o número mínimo de moedas para satisfazer a quantidade.

Esses problemas parecem muito semelhantes, mas as soluções são muitodiferente.

Número de maneiras possíveis de fazer alterações: a subestrutura ideal para isso éDP (m, n) = DP (m-1, n) + DP (m, n-Sm) onde DP é o número de soluções para todas as moedas até a mésima moeda e a quantidade = n.

Quantidade mínima de moedas: a subestrutura ideal para isso éDP [i] = Mínimo {DP [i-d1], DP [i-d2], ... DP [i-dn]} + 1 onde i é a quantidade total e d1..dn representam cada denominação de moeda.

Por que o primeiro exigiu uma matriz 2-D e o segundo uma matriz 1-D? Por que a subestrutura ideal para o número de maneiras de fazer alterações não "DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn]"onde DP [i] é o número de maneiras pelas quais as quantias podem ser obtidas pelas moedas. Parece lógico para mim, mas produz uma resposta incorreta. Por que essa segunda dimensão para as moedas é necessária neste problema, mas não é necessária em o problema da quantidade mínima?

LINKS PARA PROBLEMAS:

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

Desde já, obrigado. Todos os sites em que vou apenas explicam como a solução funciona, e não por que outras soluções não funcionam.