0

该问题需要计算特定成本的硬币变化次数。

例如，如果我的硬币值为50, 20, 10, 5, 1，我可以形成以下成本：

5 => (5), (11111)，这是 2 种方式。

10 => (10), (5, 5), (5, 11111), (11111, 11111)，这是 4 种方式。

这是我的功能。它从 10 的成本中返回错误的结果（返回 9 种方式，而实际的方式只有 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;
}

如何修复此功能以提供正确数量的方式？这个算法是否正确？在此处查看完整的代码及其输出

注意：我的问题不在于dp数组初始化。我在每次调用之前都memset将其初始化为.-1rec

4

3 回答 3

3

(5, 1, 1, 1, 1, 1) 和 (1, 1, 1, 5, 1, 1) 在你的算法中是不同的方式，你应该让它减少。

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));
}
于 2012-08-08T09:17:42.060 回答
1

结果是错误的，因为您永远无法确保您的算法从 5 个硬币开始。(5,11111) 在您的代码中与 (1, 5, 1111) 一样有效，但结果相同。你的结果应该是错误的 6 和更高，而不是 10 和更高。

要解决这个问题，你可以在你的函数 rec() 中做一个截止：

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

应该这样做。

编辑：你将不得不照顾你的 dp[] 数组，因为它不关心这个截止，但这通常是你遇到的错误。您可以评论该行，并检查这是否有效。

于 2012-08-08T09:08:46.923 回答
1

一句话：你的初始化

memset(dp, -1, sizeof dp);

不是很安全。memset初始化内存空间的每个字节（参见http://www.cplusplus.com/reference/clibrary/cstring/memset/。）。对于这种特殊情况，您很幸运，并且 的表示int(-1)（可能）与四次相同unsigned char(-1)。

我建议使用std::fill（http://www.cplusplus.com/reference/algorithm/fill/）。

于 2012-08-08T09:12:18.487 回答