DP -硬币兑换计数

Question

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

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

5 => (5)，(11111)，这是两种途径。

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

这是我的功能。它正在从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之前，我每次都使用-1将其初始化为rec。

Answer 1

(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));
}

Answer 2

结果是错误的，因为你从来没有确保你的算法开始于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[]数组，因为它不关心这个截止值，但这通常是您遇到的错误。您可以注释这一行，并检查这是否有效。

Answer 3

注意:你的初始化

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/ )。