recursion - 为什么我不能在硬币找零 dp 中重复使用相同的硬币？

Question

例子：

给定 20 美元，我想计算用硬币兑换 20 美元的方式 = { 5$,10$, 15$} 硬币的顺序无关紧要。

解决方案在这里

解决方案说：总方式数 = 使用硬币 + 不使用硬币： total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

以树的形式：

Answer 1

解决方案说：总方式数 = 使用硬币 + 不使用硬币： total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

我认为您误解了解决方案声明。

它确切地说是：

1) Optimal Substructure
To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.

这是一种将问题细分为同一问题的两个较小版本的方法。

在不使用硬币的情况下可以完成的方法的数量只是相同的问题具有相同的目标总数和较小的硬币集。

但是用至少一个这个硬币可以完成的方法的数量是相同的问题，目标总数减少了硬币的大小，但使用相同的一组允许的硬币。

在这第二组中，确实允许再次使用相同的硬币。