emmm,一不小心捣鼓出来一个O(n)的算法…… 用数组count[i]来存储能组合出i的方案数。 一共四种硬币,从1元开始,依次考虑,比如说,只用1元来组合,显然每个i都只有一种组合方案。 现在考虑加入2元,我们事先约定小的硬币在前,大的硬币在后,那么count[i]至少由一个2元硬币组成的情况下, 其方案数应该为count[i-2],这里count[i-2]已经求出来了,是由1元和2元组合成i-2元的所有方案数,所以count[i]=(count[i]+count[i-2])%mod即可。 同理,再加入5元,count[i]=(count[i]+count[i-5])%mod,10元...