100元换零钱1元2元,5元10元,20元50え有多少种组合方案
一道笔试题,当时就懵逼了。
找到递推公式之后,其实也不难
F(N,M)表示 用不超过第M个值的数来表示N 的所有组合方案
F(4,6) 的所有组合方案其实就是F(4,2)的组合方案毕竟VAL[3]~VAL[6]均大于4,不可能存在更多的组合方案
用不超过第6个值的数(即50元)来表示4元 的所有组合方案【F(4,6)】
等于 用不超过第2个值的数(即2元)来表示4元 的所有组合方案【F(4,2)】
用不超过第2个值的数(即2元)来表示4元 的所有组合方案【F(4,2)】用不超过第1個值的数(即1元)来表示4元 的所有组合方案
用不超过第3个值的数(即5元)来表示2元 的所有组合方案【F(4,1)+F(2,3)】
F(0,0)可以理解成用0元来表示0元,这算是1種方案
此时我们就能看出4的组合方案其实就是