动态规划题目（一）——换零钱

布满荆棘的人生 2022-08-06 01:07 192阅读 0赞

**动态规划题目（一）——换零钱**

# 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; 
    
    }

大家可以看出来，递归方式求解比较便于理解。当时，我们一定也要掌握非递归方式的实现，虽然它不太好想，例如上面的

arr[j] += arr[j-dimes[i]];

这一句。当时非递归方式的有效性是有目共睹的！