c++ - DP - 计数硬币变化

Question

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

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

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

如何修复此函数以提供正确的方法数？这个算法是否正确？查看完整代码及其输出 here

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

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