杨成略加思考,便给出了答案。
“找零四块有三种方式”。
“第一种,找四个1块的硬币”。
“第二种,找两个1块和一个2块的硬币”。
“第三种,找两个2块的硬币”。
大叔接着问道。
“那小伙子,假如要找零10块,而我现在有2块,3块和5块的硬币,有多少种方式呢?”
“这。。。”,杨成一时语塞。
“稍等一下”,杨成感觉大脑不够用了,于是调出代码编辑器面板。
这是一个经典的找零组合问题,这种问题如果不用递归是很难求解的。
现有硬币种类2,3,5,找零10块。
将这个问题,可以分解为2个子问题:
1包含2块硬币有多少种解法。