硬幣更換 - DP

Question

對於理解動態編程中的硬幣更換問題，我有一個小問題。 簡而言之，我必須使用最少數量的硬幣來更改金額。並且我們注意到M（j）對於量j進行改變所需的最小硬幣數量。

在上面的公式中，我不明白M（j-vi）是什麼意思。 vi必須是j-1中使用的硬幣的最大值？

Answer 1

你正在爲不同的值j製作一堆硬幣，命名爲M（j）。 M的點（j - v _i）是要考慮一個價值硬幣v _i，那麼你將它添加到以達到值j？當然，因爲那加上你正在考慮的硬幣加起來就是j值。

當然，我們的目標是儘可能少地使用硬幣，因此您可以通過在其上添加一枚硬幣v _i來擴大其範圍，以達到值j。這就是min所做的。 +1，因爲您將硬幣添加到樁上以形成新樁M（j）。

Answer 2

加上一個意味着你正在消耗一個硬幣，因此你所做的總變化會減少所增加硬幣的數量，這就是爲什麼原始j值減少的原因。