SICP 换硬币问题

[BigDogWang]

SICP 有个例题，题目：

给了 50、25、10、5、1 美分的硬币，将 1 美元（ 100 美分）换成零钱，总共有多少种换法？

作者给出了一个思路：

将总数为 a 的现金换成 n 种硬币的不同方式的数目等于

• 将现金数 a 换成除第一种硬币之外的所有其他硬币的不同方式数目，加上

• 将现金数 a - d 换成所有种类的硬币的不同方式数目，其中的 d 是第一种硬币的币值

迫于数学基础太差，忘光了，实在想不出怎么根据题目得出这个思路，网上也没有靠谱的答案，都是拿着思路转迭代。 请教一下大家这个思路是怎么证明出来的

[Wincer]

这不就是动态方程吗？楼主可以搜一下动态规划的解题步骤

[BigDogWang]

@Wincer 我去看看