如何用大型輸入進行動態編程

Question

假設我們現在正在解決可以通過動態編程解決的典型問題 - 獲取可能的硬幣組合的數量以進行更改。

Memorizer mem = new Memorizer(); 
int[] coins = { 100000, 8534, 5935, 291, 76, 51, 30, 29, 7, 5 } 
...... 

int getNum(int money, int idx) { 
    if(idx == coins.length - 1) { 
     if(money % coins[idx] == 0) 
      return 1; 
     else 
      return 0; 
    } 

    int found = mem.find(money, idx); 
    if(found != null) 
     return found; 

    int num = 0; 
    for(int i = 0; i <= (money/coins[idx]); i++) 
     num += getNum(money - i * coins[idx], idx + 1); 

    mem.remember(money, idx, num); 

    return num; 
} 

但是，如果這筆錢非常大，大約20億美元，那麼很難記住所有的中間結果。我怎樣才能用非常大的輸入來解決問題？請幫幫我。謝謝。

Answer 1

也有一些是不對的DP，它應該是：

if(money % coins[idx] == 0) 
    return money/coins[idx]; 

話雖這麼說，這是壞主意環上一個硬幣的價值，直到你到達的錢，相反，遍歷所有的值的硬幣。這樣，num [x] = min（num [x-coin [i]] +1，num [x]）。

在這段代碼中，我們可以在數組的一部分上使用記憶，即last {coin}元素的最大值，因爲只需要記住x-coin [i]。嘗試找出如何實現這一點，如果它是你正在尋找。