問(wèn)題來(lái)源

這是Hackerrank上的一個(gè)比較有意思的問(wèn)題，詳見(jiàn)下面的鏈接：
https://www.hackerrank.com/challenges/ctci-coin-change

問(wèn)題簡(jiǎn)述

給定m個(gè)不同面額的硬幣，C={c₀, c₁, c₂…c_m-1}，找到共有幾種不同的組合可以使得數(shù)額為n的錢換成等額的硬幣（每種硬幣可以重復(fù)使用）。
比如：給定m=3，C={2,1,3}，n=4，那么共有4種不同的組合可以換算硬幣

{1,1,1,1}

{1,1,2}

{2,2}

{1,3}

解決方案

基本思路是從硬幣（coins）的角度出發(fā)，考慮coins[0]僅使用1次的情況下有幾種組合，coins[0]僅使用2次的情況下有幾種組合，依次類推，直到 (n - coins[0] * 使用次數(shù)) < 0 則終止，而每個(gè) (n - coins[0]) 下又可以遞歸 (n - coins[0] - coins[1]) 的情況，直到考慮完所有的硬幣。
這樣說(shuō)可能還是沒(méi)有說(shuō)清楚，下面以m=3，C={1,2,3}，n=4為例，用圖來(lái)說(shuō)明一下（建議結(jié)合程序一起看）。

圖1：coin Change不完整遞歸圖 上圖沒(méi)有畫出完整的遞歸過(guò)程（有點(diǎn)麻煩~偷了個(gè)懶），不過(guò)把能得出結(jié)果的幾條路徑都描繪出來(lái)了。其中，recursion(money, index)中，money指的是還沒(méi)有進(jìn)行兌換的錢，index指的是要用哪個(gè)coin去兌換，比如這里的0指的是coins[0]=1，1指的是coins[1]=2，2指的是coins[2]=3，3是不存在的，這也是程序的終止條件之一。 注意到再遞歸的過(guò)程中有重疊子問(wèn)題（我用紫色標(biāo)注出了其中一個(gè)），這就可以用動(dòng)態(tài)規(guī)劃的思想來(lái)解決了，創(chuàng)建一塊空間來(lái)存儲(chǔ)已經(jīng)算過(guò)的結(jié)果就可以了。 # 程序代碼 好了，下面直接上程序了，結(jié)合圖看好理解~ #include <iostream> #include <unordered_map> #include <string> #include <vector>using namespace std;long long recursion(vector<int> &coins, int money, int index, unordered_map<string, int> &memo){//終止條件2個(gè)if (0 == money)return 1;if (index >= coins.size() || money < 0)return 0;string key = to_string(money) + " , " + to_string(index);//如果記錄中有的話就直接返回就好了if (memo.find(key) != memo.end())return memo[key];long long res = 0;int remaining = money;while(remaining >= 0){res += recursion(coins, remaining, index + 1, memo);remaining -= coins[index];}//記錄一下memo[key] = res;return res; }long long make_change(vector<int> coins, int money) {//用哈希表來(lái)記錄 <剩下的錢-用的硬幣>:換硬幣的組合數(shù)unordered_map<string, int> memo;long long res = recursion(coins, money, 0, memo);return res; }int main(){int n;int m;cin >> n >> m;vector<int> coins(m);for(int coins_i = 0;coins_i < m;coins_i++){cin >> coins[coins_i];}cout << make_change(coins, n) << endl;return 0; }

Sample Input

10 4 2 5 3 6

Sample Output

5

真正的DP

上面的那段代碼是以自頂向下的方式來(lái)解決問(wèn)題的，思路比較清晰，而真正的動(dòng)態(tài)規(guī)劃是自底向上的，思路其實(shí)也差不多，下面給出代碼~

long long make_change(vector<int> coins, int money) {vector<long long> memo(money + 1, 0);memo[0] = 1;for (int i = 0; i < coins.size(); i++){for (int j = coins[i]; j <= money; j++){memo[j] += memo[j - coins[i]];}}return memo[money]; }

補(bǔ)充——硬幣不能重復(fù)使用

如果每種硬幣不能重復(fù)使用的話，又該怎么辦呢？這只需要再程序上做一些小的改動(dòng)就可以了，真的是非常神奇~
要細(xì)細(xì)體會(huì)一下~

long long make_change(vector<int> coins, int money) {vector<long long> memo(money + 1, 0);memo[0] = 1;for (int i = 0; i < coins.size(); i++){//改動(dòng)處：由從前往后改成了從后往前，略去了重復(fù)的情況for (int j = money; j >= coins[i]; j--){memo[j] += memo[j - coins[i]];}}return memo[money]; }

補(bǔ)充2——不同順序表示不同組合

然后再來(lái)變一變，如果每種硬幣可以使用無(wú)限多次，但是不同的順序表示不同的組合，那么又有多少種組合呢？
比如：

coins = [1, 2, 3] money = 4可能的組合情況有： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)注意，不同的順序序列表示不同的組合~所以結(jié)果是7。

這種情況下的代碼是：

long long make_change(vector<int> coins, int money) {vector<long long> memo(money + 1, 0);memo[0] = 1;//改變了里外循環(huán)的順序for (int i = 1; i <=money; i++){for (int j = 0; j < coins.size(); j++){if (i - coins[j] >= 0)memo[i] += memo[i - coins[j]];}}return memo[money]; }

要仔細(xì)體會(huì)一下三種情況下的區(qū)別和代碼微妙的變化~

結(jié)束語(yǔ)

動(dòng)態(tài)規(guī)劃的代碼量其實(shí)不大，但是思維量還是挺大的，要寫正確還是要折騰挺久的~
本人是初學(xué)者，如有錯(cuò)誤，還請(qǐng)指正~

總結(jié)

以上是生活随笔為你收集整理的利用动态规划（DP）解决 Coin Change 问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。