现在有1分、2分、5分的硬币各无限枚，要凑成1元有多少种凑法?

coins.js

function getResult(n,coins) {

    var a = new Array(n+1);

    for(var i = 0; i <= n;i++)
        a[i] = 0;

    a[0] = 1;

    for(var j = 0; j<coins.length; j++)
        for(var i = 0; i <= n;i++)        
             a[i+coins[j]] += a[i]; 

    return a[n];

}
getResult(100,[1,2,5]); // 541

递归更短（已经多用局部变量了），而且更容易理解（可惜效率低）……

function getResult(n, coins, i) {
    if (n === 0) return 1;
    if (n < 0 || i >= coins.length) return 0;

    var used = getResult(n - coins[i], coins, i);
    var notUsed = getResult(n, coins, i + 1);
    return used + notUsed;
}

getResult(100, [1, 2, 5], 0);

裸写没调试，意思应该到了……

scala for表达式更简练 for (a <- 0 to 100; b <- 0 to 50; c <- 0 to 20; if (a + 2*b + 5*c == 100)) yield (a,b,c)

就题论题没有抽象

var ret = 0;
for (var i = 0; i <= Math.floor(100 / 5); i++) {
  ret += Math.floor((100 - i * 5) / 2) + 1;
}

def count(total: Int, choices: List[Int]): Int = 
    if(total == 0) 1
    else choices match {
      case 1 :: Nil => 1
      case head :: tail =>
        val loop = total / head
        (0 to loop).map { i =>
          count(total - i * head, tail)
        }.sum
}

如果是5，2，1的情况，只需考虑n个5和n个2组合小于等于100的情况即可，一次0~100/5循环中累加(100-5*n)/2 + 1即可

如果要写函数传参输入5，2，1的话，就好像那个炸掉地球的冷笑话

我啊 我一直以为序列不同 不算不同方法 鄙视

@smilingleo 的答案0分
@xibei 和 @DaniloSam 的针对有1的组合是ok的，针对这题貌似是最佳解了，不过超过三种硬币的话，复杂度增长很快
@wangzaixiang 这个复杂度也有点高哦

var icons = [5, 2, 1];

var fn = function(n,j){

if(n === 0){

return 1;

}

if(icons[j] === 1){

return 1;

}else{

var res = 0;

for(var i = 0; i <= n; i += icons[j]){

res += fn(n - i, j + 1);

}

return  res;

}

}

我早上算错了，这个效率是挺低的。好吧,我又学了一着。

@domkey 嘿嘿 教主客气鸟~

刚刚sign up了一个github account。八阶矩阵可以递推……不知道有没有更小的递推式。（一个数列的递推）

居然有这么奇葩的方法，看懂真累。。不过这代码风格很有槽点啊。。

动态规划（Dynamic Programming），这个问题属于完全背包问题那一类，还有其他像整数拆分之类的和这个代码几乎一样，只是初始条件可能会有所不同。PS：确实代码风格有一处有槽点啊，a[101..105]全是NaN:)
也许改成下面这样会好理解点。

function getResult(coins, n) {
  var a = new Array(n+1);

  for (var i = 1; i <= n; ++i) a[i] = 0;

  a[0] = 1;

  for (var i = 0; i < coins.length; ++i)
    for (var j = coins[i]; j <= n; ++j) // Here
      a[j] += a[j-coins[i]]; //  and here!

  return a[n];
}

我厂前端同学的解法（haskell）：

module Main where
    coin :: Int -> Int
    coin 0 = 0
    coin n = sum $ map (\a -> (a `div` 2 + 1)) $ takeWhile (>=0) [a | a <- [n - (5 * b) | b <- [0 .. ]]]

详见http://zhanglin.pro/19

就是动态规划吗？