想兑换100元钱,有1,2,5,10四种钱,问总共有多少兑换方法。
下面提供两种实现方式,其中代码注释的很清楚。
关于动态规划的基本原理,参考:
http://www.cnblogs.com/sdjl/articles/1274312.html
2. 递归解法
- //动态规划
- #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;
- int num2=coinExchange(N);
- cout<<num2<<endl;
- return 0;
- }
3. 非递归解法
- //动态规划
- #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;
- 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 num=coinExchangeRecursion(N, 4);
- cout<<num<<endl;
- int num2=coinExchange(N);
- cout<<num2<<endl;
- return 0;
- }
大家可以看出来,递归方式求解比较便于理解。当时,我们一定也要掌握非递归方式的实现,虽然它不太好想,例如上面的
- arr[j] += arr[j-dimes[i]];
这一句。当时非递归方式的有效性是有目共睹的!