一时语塞。
“稍等一下”,杨成感觉大脑不够用了,于是调出代码编辑器面板。
这是一个经典的找零组合问题,这种问题如果不用递归是很难求解的。
现有硬币种类2,3,5,找零10块。
将这个问题,可以分解为2个子问题:
1包含2块硬币有多少种解法。
2不包含2块硬币有多少种解法。
对于每个子问题,又有子问题:
1包含当前最小面值硬币有多少种解法。
2不包含当前最小面值硬币有多少种解法。
。。。。
这两个子问题的解法种类之和就是最后的答案。
编译,运行,得到结果,杨成给出了答案。
“是4种!”
“很好!”
“结账!”,中年大叔递过来4块钱。
“叮!恭喜您完成了统计找零组合的相关任务!”
“当前积分103分,击败了全球37的玩家,请您再接再厉!”
()