題目描述

想兌換100元錢，有1,2,5,10四種錢，問總共有多少兌換方法

遞歸解法

#include<iostream> using namespace std; const int N = 100; int dimes[] = {1, 2, 5, 10}; int arr[N+1] = {1}; int coinExchangeRecursion(int n, int m) //遞歸方式實現，更好理解 { if (n == 0) //跳出遞歸的條件return 1; if (n < 0 || m == 0) return 0; return (coinExchangeRecursion(n, m-1) + coinExchangeRecursion(n-dimes[m-1], m)); //分為兩種情況:換取當前面值的情況 + 沒有換取當前面值的情況 }int main() {int num=coinExchangeRecursion(N, 4); cout<<num<<endl; return 0; }

非遞歸解法

#include<iostream> using namespace std; const int N = 100; int dimes[] = {1, 2, 5, 10}; int arr[N+1] = {1}; int coinExchange(int n) //非遞歸實現 { int i, j; //i從0 ~ 3 因為每個arr[j]都要有一次是假設兌換了dimes[i]，所以我們要遍歷一次for (i = 0; i < sizeof(dimes)/sizeof(int); i++){ for (j = dimes[i]; j <= n; j++) //求，arr[j]的時候，可以看出arr[j] = arr[j] + arr[j-dimes[i]]，//對應著上面的遞歸方式：arr[j]就是coinExchangeRecursion(n, m-1)，//arr[j-dimes[i]]就是coinExchangeRecursion(n-dimes[m-1], m)arr[j] += arr[j-dimes[i]]; } return arr[n]; } int main() {int num2=coinExchange(N); cout<<num2<<endl; return 0; }

下面寫法更容易理解一些：

int coinExchange(int n) //非遞歸實現 { int i, j; for(i=1; i<=n; i++){for (j=0; j<sizeof(dimes)/sizeof(int); i++){if (i>=dimes[j])arr[i] += arr[i-dimes[j]]}}return arr[n]; }

方法總結

動態規劃的經典之處把大問題分解成幾個小問題解決
遞歸算法:100元的換法:零錢中有此面值與零錢中沒此面值的兩種情況，注意遞歸結束的條件
非遞歸算法:換100的零錢,那么先從換1、2、……的零錢算起,這個算法,最好轉換成臺階走法的問題來理解
仔細推理可以看出arr[j] = arr[j-dimes[0]] + arr[j-dimes[1]] + arr[j-dimes[2]] + arr[j-dimes[3]] (j-dimes[i]>=0)

#include<iostream> #include<vector> //std::vector #include <algorithm> //std::count using namespace std; const int N = 100; int dimes[] = {1, 2, 5, 10}; int arr[N+1] = {1}; vector<int> vv; int coinExchangeRecursion(int n, int m) //遞歸方式實現，更好理解 { if (n == 0) {int i;for (i = 0; i < sizeof(dimes)/sizeof(int); i++) {int cnt = count(vv.begin(), vv.end(), dimes[i]);cout << dimes[i] << ": " << cnt << "\t";}cout << endl;return 1; } //跳出遞歸的條件if (n < 0 || m == 0) return 0;vv.push_back(dimes[m-1]);int yes = coinExchangeRecursion(n-dimes[m-1], m);vv.pop_back();int no = coinExchangeRecursion(n, m-1);return (no+yes); //分為兩種情況，如果沒有換當前硬幣，那么是多少？加上，如果換了當前硬幣，總值減少，此時又是多少種兌換方法？ }int coinExchange(int n) //非遞歸實現 { int i, j; for (i = 0; i < sizeof(dimes)/sizeof(int); i++) //i從0 ~ 3 因為每個arr[j]都要有一次是假設兌換了dimes[i]，所以我們要遍歷一次{ for (j = dimes[i]; j <= n; j++) //求，arr[j]的時候，可以看出arr[j] = arr[j] + arr[j-dimes[i]]，//對應著上面的遞歸方式：arr[j]就是 coinExchangeRecursion(n, m-1)，//arr[j-dimes[i]]就是coinExchangeRecursion(n-dimes[m-1], m)arr[j] += arr[j-dimes[i]]; } return arr[n]; } int main(int argc, char *argv[]) {int num=coinExchangeRecursion(N, 4); cout<<num<<endl; int num2=coinExchange(N); cout<<num2<<endl; return 0; }

參考:

• http://www.tuicool.com/articles/VBreAnY
• http://taop.marchtea.com/02.05.html
• 動態規劃:從新手到專家

總結

以上是生活随笔為你收集整理的动态规划--换零钱的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。