如何计算硬币变化中的不同组合？ [重复]

Question

这个问题在这里已有答案：

• Dynamic Programming - Number of distinct combinations to reach a given score 1回答

long long num(long long p)
{
   if(p<0)
      return 0;
   if(p==0)
      return 1;
   if(t[p]!=0)
      return t[p];
   t[p]=num(p-1)+num(p-2)+num(p-5)+num(p-10)+num(p-20)+num(p-50)+num(p-100);
   return t[p];
}

我使用这种方法num来计算硬币变化问题的可能方式的数量。问题是这种方法将1,1,2和1,2,1计为不同，应该被视为1.如何做到这一点？无处不在找到任何好的解决方案

Answer 1

这是不同硬币组合数量的C ++实现。

int combo(int d[], int r, int R)
{
    if (R == 0)
        return 1;
    if (R < 0)
        return 0;

    int tot = 0;

    for (int i = 0; i < r; i++) 
        tot += combo(d, r, R - d[i]);

    return tot;
}

希望这可以帮助。