硬币找零-DP [英] Coin change - DP

问题描述

我在理解动态编程中的硬币找零问题时遇到了一个小问题。简单地说，我必须使用最少数量的硬币来更改总和。

I have a small problem understanding the coin change problem in dynamic programming. Simply put, I have to change a sum using a minimum number of coins.

我有n个面额为1 = v1的硬币。 v2< ...< vn，我们注意到M（j）更改金额j所需的最小硬币数量。

I have n denominations of coins of values 1 = v1 < v2 < ... < vn, and we note M(j) the minimum number of coins required to make change for amount j.

在上面的公式中，我不了解M（j-vi）的含义。 vi必须是j-1中使用的硬币的最大值吗？

In the above formula I don't understand what M(j-vi) means. vi has to be the maximum value of the coins used in j-1?

推荐答案

您要制造成堆的不同硬币值j，名为M（j）。 M（j-v _i ）的要点是考虑一个值v _i 的硬币，那么您将其添加到哪一堆中才能达到值j？当然，值j的堆-v _i ，因为那加上您正在考虑的硬币，现在就等于值j。

You're making piles of coins for different values j, named M(j). The point of M(j - v_i) is to consider a coin of value v_i, then which pile do you add it to in order to reach the value j? The pile with value j - v_i of course, because that plus the coin you're considering now add up to the value j.

当然，目标是要拥有尽可能少的硬币，因此，通过添加v _{的硬币，可以获取可以扩展到达到值 j 的最小桩我}。这就是分钟的作用。 +1是因为将硬币v _i 添加到桩中以形成新桩M（j）。

Of course the goal is to have as few as possible coins, so you take the smallest pile that you can extend to reach the value j by adding a coin of v_i to it. That's what the min does. +1 because you add the coin v_i to the pile to form the new pile M(j).

这篇关于硬币找零-DP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！