DP货币找零解释

Question

硬币找零是一个非常流行的问题，它询问了使用硬币（C [0]，C [1] ... C [K-1]）如何到达 N 美分的数量。DP解决方案是使用方法s(N, K) = s(N, K-1) + s(N-C[K-1], K)，其中s(N,K)是使用前K个硬币（按升序排序）到达和为N的方式的数量。这意味着使用前K个硬币制作N美分的方式数量等于到达相同和而不使用第K个硬币的方式数量加上到达N-第K个硬币的方式数量的总和。我真的不明白您是如何得出此解决方案的，以及它在逻辑上是如何有意义的。能有人解释一下吗？

- arilato

---

s[n,k] 要么使用第 k 个元素（即 s[n-c[k-1],k]），要么不使用（即 s[n, k-1]）。 - Herokiller

Answer 1

解决 DP 问题时最重要的事情是将问题简化为一组更简单的子问题。大多数情况下，“更简单”意味着具有较小的参数，对于这种情况，如果总和较小或剩余硬币价值较小，则问题更简单。

我解决这个问题的方式是：好的，我有一组硬币，我需要计算出可以形成给定总和的方式数量。听起来很复杂，但如果我少一个硬币就会变得容易一些。

同时，考虑底层情况也有所帮助。在这种情况下，如果你只有一个硬币，你知道可以以多少种方式组成给定总和。这种情况暗示了将问题简化为更简单的问题可能会减少不同硬币的数量。

- Ivaylo Strandjev

---

谢谢，直到我看了你的回答才恍然大悟 :P 临时抽风了。 - arilato