第四十五章 统计找零组合

编程之战 程序小猿 492 字 2024-05-17

杨成略加思考,便给出了答案。

“找零四块有三种方式”。

“第一种,找四个1块的硬币”。

“第二种,找两个1块和一个2块的硬币”。

“第三种,找两个2块的硬币”。

大叔接着问道。

“那小伙子,假如要找零10块,而我现在有2块,3块和5块的硬币,有多少种方式呢?”

“这。。。”,杨成一时语塞。

“稍等一下”,杨成感觉大脑不够用了,于是调出代码编辑器面板。

这是一个经典的找零组合问题,这种问题如果不用递归是很难求解的。

现有硬币种类2,3,5,找零10块。

将这个问题,可以分解为2个子问题:

1包含2块硬币有多少种解法。