algorithm - DP币变化说明

Question

硬币找零是一个非常流行的问题，它询问有多少种方法可以使用硬币（C[0]、C[1]...C[K-1]）得到 N 美分的总和。DP的解决方法是使用s(N, K) = s(N, K-1) + s(NC[K-1], K)的方法，其中s(N,K)是到达的路数与前 K 个硬币的总和为 N（按升序排序）。这意味着使用前 K 个硬币赚取 N 美分的方法的数量是在不使用第 K 个硬币的情况下达到相同总和的方法数量加上获得 N-第 K 个硬币的方法数量的总和。我真的不明白你怎么会遇到这个解决方案，以及它在逻辑上的意义。有人可以解释一下吗？

Answer 1

解决 DP 时最重要的事情是将问题简化为一组更简单的子问题。大多数情况下，“更简单”意味着使用更小的参数，在这种情况下，如果总和更小或剩余的硬币值更少，问题就会更简单。

我解决问题的思路是：好的，我有一组硬币，我需要计算可以形成给定总和的方法的数量。这听起来很复杂，但如果我少一枚硬币，那就容易一些了。

考虑底壳也有帮助。在这种情况下，您知道如果您只有一枚硬币，您可以通过多少种方式形成一个给定的总和。这以某种方式表明减少到更简单的问题可能会减少不同硬币的数量。