1

我正在尝试了解硬币找零问题的解决方案，但遇到了一些困难。

在Algorithmist中，有一个动态规划解决方案的伪代码解决方案，如下所示：

n = goal number
S = [S1, S2, S3 ... Sm]

function sequence(n, m)
   //initialize base cases

   for i = 0 to n
     for j = 0 to m
       table[i][j] = table[i-S[j]][j] + table[i][j-1]

这是一个非常标准的O(n^2)算法，可以避免使用二维数组多次重新计算相同的答案。

我的问题有两个：

  1. 如何定义基本案例并将它们合并table[][]为初始值
  2. 如何从表中提取不同的序列

关于问题 1，此算法存在三种基本情况：

  • if n==0, return 1
  • if n < 0, return 0
  • if n >= 1 && m <= 0, return 0

如何将它们合并到table[][]中，我不确定。最后，我不知道如何从数组中提取解决方案集。

4

1 回答 1

2

我们可以用至少两种不同的方法来实现动态规划算法。一种是使用记忆的自上而下的方法，另一种是自下而上的迭代方法。

对于动态编程的初学者，我总是建议首先使用自顶向下的方法，因为这将有助于他们理解动态编程中的递归关系。

所以为了解决换币问题，你已经明白递推关系说的是什么了：

table[i][j] = table[i-S[j]][j] + table[i][j-1]

这样的递归关系很好，但没有那么明确，因为它没有任何边界条件。因此，我们需要定义边界条件，以确保递归关系能够成功终止而不会陷入无限循环。

那么当我们尝试沿着递归树向下走时会发生什么？

如果我们需要计算，这意味着使用硬币从 typetable[i][j]更改为 的方法的数量，我们需要处理几个极端情况：i0j

1）如果j == 0？

如果j == 0我们将尝试解决子问题table(i,j-1)，这不是一个有效的子问题。因此，一个边界条件是：

if(j==0) {
  if(i==0) table[i][j] = 1;
  else table[i][j] = 0;
}

2）如果i - S[j] < 0？

我们还需要处理这种边界情况，我们知道在这种情况下，我们要么不尝试解决这个子问题，要么table(i-S[j],j) = 0对所有这些情况进行初始化。

所以总而言之，如果我们要从自上而下的记忆方法实现这种动态编程，我们可以这样做：

int f(int i, int j) {
  if(calc[i][j]) return table[i][j];
  calc[i][j] = true;
  if(j==0) {
    if(i==0) return table[i][j]=1;
    else return table[i][j]=0;
  }
  if(i>=S[j])
    return table[i][j]=table[i-S[j][j]+table[i][j-1];
  else
    return table[i][j]=table[i][j-1];
}

在实践中，我们也可以使用table数组的值来帮助跟踪之前是否计算过这个子问题（例如，我们可以初始化一个值 -1 表示这个子问题还没有被计算过）。

希望答案是明确的。:)

于 2013-02-09T00:30:53.480 回答