硬币更换算法和伪代码：需要澄清

Question

我试图了解硬币更换问题的解决方案，但我有一些困难。

在the 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)算法避免通过使用2-d阵列多次重新计算相同的答案。

我的问题是双重的：

1. 如何定义基例和在table[][]其纳入作为初始值
2. 如何从表中提取出不同的序列

关于问题1，该算法有三种基本情况：

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

如何将其纳入table[][]，我不知道。最后，我不知道如何从数组中提取出解决方案。

Answer 1

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

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

因此，为了解决硬币变化问题，你已经明白了复发的关系说：

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

这样的复发的关系是好的，但不是明确的，因为它不有任何边界条件。因此，我们需要定义边界条件以确保重复关系可以成功终止而不会进入无限循环。

那么当我们尝试去递归树时会发生什么？

如果我们需要计算table[i][j]，这意味着途径数量从0类型更改i使用硬币j，有几个角落情况下，我们需要处理：

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的值意味着这个子问题还没有被计算）。

希望答案很清楚。 :)