硬币兑换自底向上动态规划

Question

http://uva.onlinejudge.org/external/6/674.html我正在努力解决这个问题。不过，请注意，这不是最小硬币更换问题，它要求我使用50, 25, 15, 10, 5和1美分硬币制作N美分的不同方法。它相当简单，所以我做了这个函数：

int count(int n, int m) // n is the N of the problem, m is the number of coin types and s[] is {1, 5, 10, 25, 50}
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  return DP[n][m - 1] + DP[n - s[m]][m];
}

同样简单的是添加动态编程和备忘录：

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

然而，这些都不够快-我需要自下而上的动态规划，但我在编码它时遇到困难，即使在算法学家的帮助下-http://www.algorithmist.com/index.php/Coin_Change.

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

出于某种原因，我得到的每个结果都是0，这是我的完整代码：

#include <stdio.h>
#include <string.h>

using namespace std;

#define MAX 7490

int s[] = {1, 5, 10, 25, 50}, m = 5, input, DP[MAX][5], i, u;

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

int main()
{
  memset(DP, -1, sizeof DP);
  generate();

  while (scanf("%d", &input) != EOF)
  {
    //printf("%d\n", count(input, 4));
    printf("%d\n", DP[input][4]);
  }

  return 0;
}

Answer 1

你在这里犯了错误：

else if (u == 0)
{
   DP[i][u] = 0;
}

它应该是DP[i][u]=1，因为你可以用1分硬币以1种可能的方式产生任何值i。i、 e.取5美分，你将取5枚1美分的硬币，这是总共5美分的一种方式。

顺便说一句，在你的第一种计数方法中，你有以下几点：

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
  return count(n, m - 1) + count(n - s[m], m);
}

或者这个：

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
    return DP[n][m] = count(n, m - 1) + count(n - s[m], m);
}

如果您没有将已计算的结果进行记忆，则此记忆检查如果（DP[n][m-1]=-1 | | DP[n-s[m]][m]=-1）将永远无法工作，这可能是您的第一种方法太慢的原因：-？