DP - 计数硬币找零 [英] DP - Counting coin change

问题描述

这个问题，需要计算的硬币数量的变化对特定的成本。

The problem requires to count number of coin changes for a particular cost.

例如，如果我有硬币值50，20，10，5，1 ，我能形成的费用：

For example, if I have coin values of 50, 20, 10, 5, 1, I can form costs of:

5 =>（5），（11111），其中有2种方式。

5 => (5), (11111), which are 2 ways.

10 =>（10），（5,5），（5，11111），（11111，11111），这是4种方式。

10 => (10), (5, 5), (5, 11111), (11111, 11111), which are 4 ways.

下面是我的功能。它返回错误结果从10乞讨成本（收益9种方式，而方式的实际数量仅为4）

Here is my function. It is returning wrong results begging from cost of 10 (returns 9 ways while the actual number of ways is only 4)

int dp[10000];
int coins[] = { 50, 20, 10, 5, 1 };
int rec(int n)
{
  if (n == 0) return 1;
  if (dp[n] != -1) return dp[n];
  int cnt = 0;
  for (int i = 0; i < 5; i++)
    if (coins[i] <= n) cnt += rec(n - coins[i]);
  return dp[n] = cnt;
}

我怎样才能解决这个功能给的方法是否正确？这是正确的算法，即使是？看到完整的code，其输出这里

注意：我的问题是不是与 DP 数组初始化。我使用 memset的将其每次拨打电话前先 REC 1 C $ C>。

NOTE: my problem is not with dp array initialization. I am using memset to initialize it to -1 each time before calling rec.

推荐答案

（5，1，1，1，1，1）和（1，1，1，5，1，1）在你的算法不同的方式，你应该保持它的下降。

(5, 1, 1, 1, 1, 1) and (1, 1, 1, 5, 1, 1) is different way in you algorithm, you should keep it decreasing.

int dp[10000][5];  // dp[20][2] means, if the biggest coin is coins[2],
                   // how much ways for 20 ?
int coins[] = { 1, 5, 10, 20, 50 }; // here
int rec(int n, int m)
{
  int cnt = 0;
  int i;
  if (n == 0) return 1;
  //if (m == 0) return 1;
  if (dp[n][m] != -1) return dp[n][m];
  for (i = 0; i <= m; i++)
    if (coins[i] <= n) cnt += rec(n - coins[i], i);
  return dp[n][m] = cnt;
}

int main()
{
        memset(dp, -1, sizeof(dp));
        printf("%d\n", rec(10, 4));
}

这篇关于DP - 计数硬币找零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！