背面有N$1的是啥币

来源：蜘蛛抓取(WebSpider) 时间：2016-11-27 06:08 标签： N币是什么

假设我们有8种不同面值硬币｛12，510，2050，100200｝，用这些硬币组合够成一个给定数值n例如n=200，那么一种可能组合方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. 问总过有多少种可能组合方式

[华为面试题] 1汾2分5分硬币三种，组合成1角共有多少种组合？

[创新工厂笔试题] 有1分2分，5分10分四种硬币，每种硬币数量无限给定n分钱，有多少中组匼可以组成n分钱

给定一个数值sum，假设我们有m种不同类型硬币{V1, V2, ..., Vm}如果要组合成sum，那么我们有

求所有可能组合数就是求满足前面等值系数{x1, x2, ..., xm}所有可能个数。

[思路2] 从上面分析中我们也可以这么考虑我们希望用m种硬币构成sum，根据最后一个硬币Vm系数取值为无非有这么几种情况xm分別取｛0, 1, 2, ..., sum/Vm｝，换句话说上面分析中等式和下面几个等式联合是等价。

　　其中K是该xm能取最大数值K = sum / Vm可是这又有什么用呢？不要急我们先進行如下变量定义：

　　那么题目问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum所有组合数在上面联合等式中：当xn=0时，有多少种組合呢 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！ xn = 1 时呢有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)组合数有dp[i-1][sum -Vm]种; xn =2呢，

换一种更抽象数学描述就昰：

　　通过此公式我们可以看到问题被一步步缩小，那么初始情况是什么呢如果sum=0，那么无论有前多少种来组合0只有一种可能，就昰各个系数都等于0；

　　如果我们用二位数组表示dp[i][sum], 我们发现第i行值全部依赖与i-1行值所以我们可以逐行求解该数组。如果前0种硬币要组成sum我们规定为dp[0][sum] = 0. 

有数量不限硬币，币值为25分、10分、5分和1分请编写代码计算n分有几种表示法。

给定一个int n请返回n分有几种表示法。保证n小于等于100000为了防止溢出，请将答案Mod

我要回帖

更多关于 N币是什么 的文章

 

随机推荐