我在理解各種問題的動態(tài)編程解決方案時遇到問題，特別是硬幣找零問題：

“給定值N，如果我們要N分錢找零，并且我們有無限數(shù)量的S = {S1，S2，..，Sm}硬幣的供應(yīng)，我們可以用幾種方法進行找零？硬幣沒關(guān)系。

例如，對于N = 4和S = {1,2,3}，有四個解：{1,1,1,1}，{1,1,2}，{2,2}，{1， 3}。因此輸出應(yīng)為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}。因此輸出應(yīng)為5。”

此問題還有另一個變體，解決方案是滿足該數(shù)量的最小硬幣數(shù)量。

這些問題看起來非常相似，但是解決方案卻非常 不同 。

進行更改的可能方法的數(shù)量：最佳的子結(jié)構(gòu)為 DP(m，n)= DP(m-1，n)+ DP(m，n-Sm)

，其中DP是所有硬幣的解數(shù)，直至第m個硬幣，金額= n。

最小數(shù)量的硬幣：最優(yōu)的子結(jié)構(gòu)是 DP [i] = Min {DP [i-d1]，DP [i-d2]，… DP [i-dn]} + 1

其中，i是總量和d1..dn代表每種硬幣面額。

為什么第一個需要二維數(shù)組，而第二個需要1-D數(shù)組呢？為什么更改方式的最優(yōu)子結(jié)構(gòu)不是“ DP [i] = DP [i-d1] + DP [i-d2] +

… DP [i-dn] ”，其中DP

[i]是我可以通過硬幣獲得數(shù)量的方法的數(shù)量。這對我來說聽起來合乎邏輯，但會產(chǎn)生錯誤的答案。為什么在此問題中需要硬幣的第二維，而在最小金額問題中卻不需要？

問題鏈接：

提前致謝。我訪問的每個網(wǎng)站僅說明該解決方案的工作原理，而不說明其他解決方案為何不工作。

總結(jié)

以上是生活随笔為你收集整理的java动态编程解决分硬币问题,动态编程硬币更改问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。