硬幣更改記憶

Question

以下算法是否找到了對特定金額進行更改的所有可能方法，是否真的使用記憶？

func count(n, m) 
    for i from 0 to n 
    for j from 0 to m 
     if i equals 0 
     table[i,j] = 1   
     else if j equals 0 
     table [i,j] = 0 
     else if S_j greater than i 
     table[ i, j ] = table[ i, j - 1 ] 
     else 
     table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ] 
return table[ n, m ] 

每次函數計數被調用時，它都會從頭開始填充表。即使表已被初始化爲某些值，下一次計數被調用，它將不會使用這些值，但會從i = 0和j = 0再次開始。

Answer 1

這不是記憶。這是動態編程代碼的一個例子。

爲了分析你的代碼，首先我們需要區分Memoization和Dynamic Programming。

記憶是一種自上而下的方法，其中動態規劃是一種自下而上的方法。

想想找到一個數字階乘的問題n。

如果您發現n！通過使用以下事實，

n! = n * (n-1)! and 0!=1 

這是自頂向下方法的示例。

將n的值保存在內存中，直到值爲0！到（n-1）！返回。缺點是你浪費了大量的堆棧內存。好處是，如果已經解決了問題，則不必重新計算子問題。子問題的解決方案存儲在內存中。

但是在你的問題中，你沒有自頂向下的方法，因此沒有記憶。

表中的每個條目都直接從以前計算的子問題解決方案中獲得。因爲它使用了自下而上的方法。因此你有一段使用動態編程的代碼。