更改硬幣執行問題

嘗試使用DP解決此經典問題時遇到了實現問題。問題給出了一組硬幣，並返回進行更改的方式數量。更改硬幣執行問題

的DP方程是類似如下： DP [I] + = DP [I - 硬幣[J]]
其中DP [I]表示的找零對於i的方式的數量。

下面是一個簡單的實現方式中，這是不正確：

int make_change_wrong(int coin[], int size, int change) { 
    vector<int> DP(change + 1, 0); 
    DP[0] = 1; 

    for (int i = 1; i <= change; ++i) { 
     for (int j = 0; j < size; ++j) { 
      if (i - coin[j] >= 0) { 
       DP[i] += DP[i - coin[j]]; 
      } 
     } 
    } 

    return DP[change]; 
}

給定的輸入： INT硬幣[] = {1,5} 變化= 6

make_change_wrong（硬幣，2， 6）返回3，但2是正確的。

使用相同的邏輯，我在這一個不太直觀的方式重新編寫，並得到正確的答案：

int make_change(int coin[], int size, int change) { 
    vector<int> DP(change + 1, 0); 
    DP[0] = 1; 

    for (int i = 0; i < size; ++i) { 
     for (int j = coin[i]; j <= change; ++j) { 
      DP[j] += DP[j - coin[i]]; 
     } 
    } 

    return DP[change]; 
}

這困擾了我很多，因爲對我來說，他們是同樣的事情... 有人可以說明兩個實現中的問題嗎？

來源

2013-07-05 galactica

如果你在兩個實現之間得到不同的答案，那麼顯然它們不是等價的。也許你可以插入一些調試語句來打印DP數組的內容，這可能有助於說明它們的不同之處。 –

感謝Brian，我知道第一個函數計數{1,1,1,1,1}兩次，但我不明白爲什麼第二個計數正確 - 他們似乎只用兩種不同的方式編碼。 – galactica

你的第一個算法是錯誤的。

DP [5] = 2 {1,1,1,1,1}，{5}

DP [6] = DP [5] + DP [1] = 3

你正在計算{5,1}兩次。 EDITED 因此，對於這樣的標準技巧是，你讓你被允許使用

DP[i,m] = DP[i-coin[m],m] + DP[i,m-1]

面額的計數這意味着使用硬幣在區間[我量的變化的方式數1..M。這很明顯，你要麼使用第m個面額，否則你不。

你正在使用的第二種算法是做同樣的技巧，但這是一個非常聰明的方法來做到這一點，拿ith硬幣，看看你可以使用它產生的所有變化。這將避免過度計數，因爲您避免執行諸如{1,5}和{5,1}之類的操作。

來源

2013-07-05 05:08:36 sukunrt

謝謝sukunrt，我明白我的第一個函數得到這個輸入錯誤，它計數{1,1,1,1,1}兩次。我不明白爲什麼使用相同想法的編碼會產生不同的行爲。 – galactica

這個問題出現在面試準備書破解編碼採訪，本書給出的解決方案根本沒有優化。它使用遞歸（沒有DP）重複計算子問題，因此運行在O（N^3）中，這是特別具有諷刺意味的，因爲它是動態編程章節的一部分。

這是一個非常簡單的工作解決方案（Java），它使用DP並在O（N）時間內運行。

static int numCombos(int n) { 
    int[] dyn = new int[n + 1]; 
    Arrays.fill(dyn, 0); 
    dyn[0] = 1; 
    for (int i = 1; i <= n; i++) dyn[i] += dyn[i - 1]; 
    for (int i = 5; i <= n; i++) dyn[i] += dyn[i - 5]; 
    for (int i = 10; i <= n; i++) dyn[i] += dyn[i - 10]; 
    for (int i = 25; i <= n; i++) dyn[i] += dyn[i - 25]; 
    return dyn[n]; 
}

來源

2013-07-26 04:16:34 The111

關於CCI書The111的不錯觀察！對於許多問題，我認爲提供的解決方案不太「整潔」。你的代碼和我的第二次嘗試是一樣的。關於DP的一件事是，即使我們成功地獲得了遞歸方程，但正確實施它仍然很棘手。 – galactica

那麼請輸入你的第二個方法：

coin[5] = {1,5,10,20,30}; 
make_change(coin,5,30);

它返回21.請檢查我的測試案例。

來源

2013-10-21 12:40:35 Mahfuz

更改硬幣執行問題

回答

相關問題