題目：換錢的方法數(shù)

? ? ? ?給定數(shù)組 arr, arr中所有的值都為正數(shù)且不重復(fù)。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數(shù)aim代表要找的錢數(shù)，求換錢有多少種方法。

將原文的偽代碼進行C++實現(xiàn)

程序員代碼面試指南第四章遞歸和動態(tài)規(guī)劃 ?點擊打開鏈接

例1：arr = [5, 10, 25, 1] ,aim = 15， 6種方法

1) 3張5元； 2）1張10元+1張5元； 3）1張10元+5張1元； 4）10張1元+1張5元；5）2張5元+5張1元； 6）15張1元

注：暴力遞歸和記憶化搜索方法，見前文?動態(tài)規(guī)劃C++實現(xiàn)--換錢的方法數(shù)（一）（暴力遞歸 和 記憶化搜索）

總結(jié)：

• ? 暴力遞歸 ? ? ? ? ? ? ? ? ? 時間復(fù)雜度 O（aim^N）
• ? 記憶化搜索 ? ? ? ? ? ? ? 時間復(fù)雜度 O （N*aim^2）
• ? 動態(tài)規(guī)劃 ? ? ? ? ? ? ? ? ? 時間復(fù)雜度 O （N*aim^2）
• ? 改進動態(tài)規(guī)劃 ? ? ? ? ? ?時間復(fù)雜度 O （N*aim） ? ? ?額外空間復(fù)雜度 O （N*aim）
• ? 壓縮空間的動態(tài)規(guī)劃 ? 時間復(fù)雜度?O （N*aim） ? ? 額外空間復(fù)雜度?O （aim）

3、動態(tài)規(guī)劃

動態(tài)規(guī)劃方法，生成函數(shù)為 N、列數(shù)為 aim+1的二維矩陣dp。（時間復(fù)雜度O(N*aim^2)）

dp[i][j] 表示在使用 arr[0,1,..,i]貨幣的情況下，組成錢數(shù)為 j 的總方法數(shù)。

第一步：邊界初始化

? ? ?dp[..][0] 表示錢數(shù)為 0， 不使用任何貨幣，所以第一列統(tǒng)一設(shè)定為1.

? ? ?dp[0][..] 表示只使用 arr[0] 的情況下，組成的錢的方法數(shù)，所以在 dp[0][arr[0]*k] = 1 ?(0 <= arr[0] * k <= aim).

第二步：中間項的更新，即求dp[i][j]

舉個例子說明更新規(guī)則：

? ? ? (1) 用 0 張 arr[i] 貨幣，只使用 arr[0,..,i-1]貨幣，方法數(shù)為dp[i-1][j].

? ? ? (1) 用 1 張 arr[i] 貨幣，只使用 arr[0,..,i-1]貨幣，方法數(shù)為dp[i-1][j-arr[i]].

? ? ? .......

? ? ? (1) 用 k 張 arr[i] 貨幣，只使用 arr[0,..,i-1]貨幣，方法數(shù)為dp[i-1][j - k*arr[i]]. ? (j - k*arr[i] >=0)

? ? ? ?dp[i][j] = dp[i-1][j-1] +?dp[i-1][j-arr[i]] + ....... +?dp[i-1][j - k*arr[i]]

? ? ? 最后dp[N-1][aim即為方法總數(shù)。

C++源碼如下：

// 換錢的方法數(shù) <動態(tài)規(guī)劃> <復(fù)雜度0(N*aim^2)> // 空間換時間，按順序進行輸出 #include<bits/stdc++.h> using namespace std; int coins3(int arr[], int aim);int main(){int N, aim; cin >> N >> aim;int arr[N];for (int i = 0; i < N; i++){cin >> arr[i];}cout << coins3(arr, aim) <<endl;return 0; }int coins3(int arr[], int aim) {int dp[sizeof(arr)][aim+1];memset(dp,0, sizeof(dp));for (int i = 0; i < sizeof(arr); i++){dp[i][0] = 1;}for (int j = 1; j * arr[0] <= aim; j++){dp[0][j*arr[0]] = 1;}int num;for (int i = 1; i < sizeof(arr); i++) {for (int j = 1; j <= aim; j++) {num = 0;for (int k = 0; j - k * arr[i] >= 0; k++) {num += dp[i - 1][j - k * arr[i]];}dp[i][j] = num;}}return dp[sizeof(arr) - 1][aim]; }

輸入：

輸出：

4、動態(tài)規(guī)劃（改進時間復(fù)雜度O（N*aim））

動態(tài)規(guī)劃方法中的第二步中進行動態(tài)更新的過程如下，思考是否存在重復(fù)計算的部分？

dp[i][j] = dp[i-1][j-1] +?dp[i-1][j-arr[i]] + ....... +?dp[i-1][j - k*arr[i]]

觀察下面遞推步驟：

dp[i][j-arr[i]] = dp[i-1][j-arr[i]] +?dp[i-1][j- 2*arr[i]] + ....... +?dp[i-1][j - k*arr[i]]

可以很容易得到動態(tài)規(guī)劃的紅色部分是等價的。那么就可以進行替換。

得到新的更新步驟：

dp[i][j] = dp[i-1][j-1] + dp[i][j -arr[i]]

C++源碼如下：

// 換錢的方法數(shù) <動態(tài)規(guī)劃> <復(fù)雜度0(N*aim)> // 空間換時間，按順序進行輸出 // dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]; #include<bits/stdc++.h> using namespace std; int coins4(int arr[], int aim);int main(){int N, aim; cin >> N >> aim;int arr[N];for (int i = 0; i < N; i++) {cin >> arr[i];}cout << coins4(arr, aim) <<endl;return 0; }int coins4(int arr[], int aim){int dp[sizeof(arr)][aim + 1];memset(dp, 0, sizeof(dp));for (int i = 0; i < sizeof(arr); i++){dp[i][0] = 1;}for (int j = 1; j * arr[0] <= aim; j++){dp[0][j * arr[0]] = 1;}for (int i = 1; i < sizeof(arr); i++) {for (int j = 1; j <= aim; j++){dp[i][j] = dp[i - 1][j];dp[i][j] += (j - arr[i]) >= 0 ? dp[i][j - arr[i]] : 0;// cout << i <<","<< j <<": "<< dp[i][j]<<endl;}}return dp[sizeof(arr) - 1][aim]; }

5、動態(tài)規(guī)劃（空間壓縮）

時間復(fù)雜度O（N*aim）,額外空間復(fù)雜度O(aim）

對于動態(tài)規(guī)劃改進方法的二維矩陣進行改進為一維矩陣，減小空間。

C++代碼如下

// 換錢的方法數(shù) <動態(tài)規(guī)劃> <復(fù)雜度0(N*aim)> // 額外空間復(fù)雜度 o(aim) #include<bits/stdc++.h> using namespace std; int coins5(int arr[], int aim);int main(){int N, aim; cin >> N >> aim;int arr[N];for (int i = 0; i < N; i++) {cin >> arr[i];}cout << coins5(arr, aim) <<endl;return 0; }int coins5(int arr[], int aim){int dp[aim + 1];memset(dp, 0, sizeof(dp));for (int j = 0; j * arr[0] <= aim; j++){dp[j * arr[0]] = 1;}for (int i = 1; i < sizeof(arr); i++) {for (int j = 1; j <= aim; j++){dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;// cout << i <<","<< j <<": "<< dp[j]<<endl;}}return dp[aim]; }以上代碼沒有考慮輸出不符合規(guī)范的問題。如有要求，需要對于輸入進行限制。

總結(jié)

以上是生活随笔為你收集整理的动态规划C++实现--换钱的方法数（二）（动态规划及其改进方法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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