在G. Polya 的名著” 如何解题” 中最后一题是: 你

在G. Polya 的名著” 如何解题” 中最后一题是: 你能用多少种方式兑换一个美元?(如果已知凑整一美元所需每一种钱币: 一分币、五分币、
一角币,二角五分币、五角币——各有多少个,就确定一种兑换方式)。
提示: 设An , Bn , Cn ,Dn , En 都是支付n 分钱的支付方式的数目
An :只用一分币
Bn :只用一分币与五分币
Cn :一分币、五分币、一角币
Dn :一分币、五分币、一角币、二角五分币
En :一分币、五分币、一角币、二角五分币、五角币
我们推出En = Dn + En−50 . 同理, Dn = Cn + Dn−25 , Cn =Bn + Cn−10 , Bn = An + Bn−5 . 该问题可以用动态规划解决, 那么,
1. 动态规划的主要特征是什么?
2. 就本题而言, 其递归算法的终止条件(也就是迭代算法的初始条
件) 是什么?
3. 你能否计算出问题的答案? 即一美元有多少种组合方式?