我们通常会对硬币更改问题采取以下递归关系：（ P 是我们需要更改的总金额， d_i 是可用的硬币）
P
d_i
但是我们不能这样做：（ V 是给定的可用硬币组， i 和 j 是它的下标， Vj 是给出的最高值硬币）
V
i
j
Vj
C[p,Vi,j] = C[p,Vi,j-1] if Vj > p = C[p-Vj,Vi,j] + 1 if Vj <=p
我写的是什么问题？虽然解决方案不是动态的，但效率不高吗？
考虑 P = 6, V = {4, 3, 1} . 你会选择 4, 1, 1 而不是 3, 3 ，所以 3 硬币而不是最佳 2 .
P = 6, V = {4, 3, 1}
4, 1, 1
3, 3
3
2
你写的内容类似于只在某些条件下有效的贪婪算法 . （见 - How to tell if greedy algorithm suffices for finding minimum coin change?） .
此外，在您的版本中，您实际上并没有在重复使用 Vi ，所以这只是浪费内存
Vi
2 回答
考虑
P = 6, V = {4, 3, 1}. 你会选择4, 1, 1而不是3, 3，所以3硬币而不是最佳2.你写的内容类似于只在某些条件下有效的贪婪算法 . （见 - How to tell if greedy algorithm suffices for finding minimum coin change?） .
此外，在您的版本中，您实际上并没有在重复使用
Vi，所以这只是浪费内存