如果我使用動態編程來解決硬幣更換，矩陣將用於記憶？

Question

對於硬幣問題的動態編程技術，矩陣應該是什麼樣子，我感到困惑。 假設我有1c，5c，10c和25c的面值，我稱之爲make-change（10）。即我想改變10美分，我最後的矩陣/陣列應該是什麼樣子。我需要知道這一點，因爲我想在程序開始時分配一個數組。我不在這裏尋找代碼。

Answer 1

我認爲一個散列圖將一個數量映射到一個硬幣列表。因此，它看起來是這樣的：

{0 =>(), 
1 => (1), 
2 => (1,1), 
3 => (1,1,1), 
... 
13 => (10,1,1,1) 
... 
} 

Answer 2

你可以用一個矩陣，其中一個維表示相加爲這你現在計算，和其他節目，其硬幣可以用 - 例如，在第一行顯示了僅使用1c個硬幣實現給定總和的方法的數量，第二行-1c和5c，第三-1c，5c和10c等等。

因此，在你的榜樣，它看起來是這樣的：

Sum: 0 1 2 3 4 5 6 7 8 9 10 
Ways: 1 1 1 1 1 1 1 1 1 1 1 (using only 1c coins - N x 1c) 
     1 1 1 1 1 2 2 2 2 2 3 (using 1c and 5c coins - either Nx1c, 1x5c + (N - 5)*1c or 2x5c) 
     1 1 1 1 1 2 2 2 2 2 4 (using 1c, 5c and 10c coins - one of the above, or 1x10c) 

你並不真的需要存儲整個矩陣雖然 - 最後一行應該永遠是不夠的。

解釋爲擺脫大多數矩陣：

只用1C硬幣時，假設你已經找到了答案（這是不是做一個非常困難的事情），它的存儲在單個陣列，說DP。現在，你有這個信息，你想知道1c和5c硬幣的答案。

您可以從sum = 0 to 10出發，保持以下不變：

• ，當你計算sum的答案，因爲之間的每個數字x在DP進入0和sum - 1包容顯示的方式，數量使用1c和5c硬幣獲得sum。所有其他條目（從sum到數組末尾）都包含僅在使用1c硬幣時的答案。

和維護它實際上是很容易的：當你計算答案x，你知道：

• 的方式來獲得x只用1C硬幣的數量 - 這是DP[x]，因爲我們還沒有覆蓋它;
• 使用至少一個5c硬幣獲得x的方法的數量 - 即DP[x - 5]，即在我們移除5c（或0，如果x - 5 < 0）之後獲得剩餘硬幣數量的方式的數量。

然後您可以將這兩個數字相加並將結果存儲在DP[x]中。然後繼續類似的其餘的硬幣。