零钱 - DP
Coin change - DP
我在理解动态规划中的硬币找零问题时遇到了一个小问题。
简而言之，我必须使用最少数量的硬币来改变一个总和。
我有 n 个面额的硬币，价值 1 = v1 < v2 < ... < vn，我们记下 M(j) 找零所需的最少硬币数量 j。
在上面的公式中我不明白 M(j-vi) 是什么意思。 vi 必须是 j-1 中使用的硬币的最大值？
加一意味着你多消耗了一个硬币，因此你所做的总变化会减少添加硬币的数量，这就是为什么原来的 j 值会减少。
你正在为不同的值 j 制作一堆硬币，命名为 M(j)。 M(j - vi)的要点是考虑一枚价值vi的硬币，那么你按顺序把它加到哪一堆达到值j？价值 j - vi 当然，因为那加上你正在考虑的硬币现在加起来价值 j.
当然我们的目标是拥有尽可能少的硬币，所以你拿最小的一堆你可以扩展到价值j通过添加一个硬币vi 给它。这就是 min 所做的。 +1 因为你将硬币 vi 添加到堆中以形成新的堆 M(j).
我在理解动态规划中的硬币找零问题时遇到了一个小问题。 简而言之，我必须使用最少数量的硬币来改变一个总和。
我有 n 个面额的硬币，价值 1 = v1 < v2 < ... < vn，我们记下 M(j) 找零所需的最少硬币数量 j。
加一意味着你多消耗了一个硬币，因此你所做的总变化会减少添加硬币的数量，这就是为什么原来的 j 值会减少。
你正在为不同的值 j 制作一堆硬币，命名为 M(j)。 M(j - vi)的要点是考虑一枚价值vi的硬币，那么你按顺序把它加到哪一堆达到值j？价值 j - vi 当然，因为那加上你正在考虑的硬币现在加起来价值 j.
当然我们的目标是拥有尽可能少的硬币，所以你拿最小的一堆你可以扩展到价值j通过添加一个硬币vi 给它。这就是 min 所做的。 +1 因为你将硬币 vi 添加到堆中以形成新的堆 M(j).