1. 题目描述

想兑换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; 
}