给定一些人民币的面额，数量不限，要求找出金额为m元且人民币张数最少的方案。这个问题既可以是一个贪心问题也可以是一个动态规划的问题。

对于现行的人民币面额：1、2、5、10、20、50、100，我们找任何金额的零钱都可以使用贪心法求解，比如找72元 = 50 + 20 + 2，3张人民币即可实现。

但如果面额发生变化的话，则用贪心算法无法求出最优解，例如面额为1、3、6、7， 要找12元的话只能是 12 = 7 + 3 + 1 + 1必须使用4张人民币，而最优解为12 = 6 + 6，两张人民币即可。因此这种问题一般使用动态规划求解。

侧面说明一点，贪心法大家都会，动态规划就不一定了！

1、动态规划解题思路

设给定的面额为x1，x2,x3。现要求找n元零钱，假设已经找好也就是你已经拿到一叠零钱，它的张数最少且总和恰好为n nn。

假设f(n)表示找n nn元钱的最少人民币张数，我们现在关注的是找的这些零钱的最后一张，它只能是

x1,x2...中的任意一张，假设最后一张为xi，那么要使总的人民币张数最少，必然要使子问题f(n-xi)最少。因此，

该状态转移方程为f(n)=min( f(n-xi) + 1)

DP:

int m[5] = {0, 1, 3, 4, 7 };  int dp(int n)  {  	if (n == 1 || n == 3 || n == 4 || n == 7)  return  1; //递归出口  	int ans = INT_MAX;  //因为求最小值，所以这里初始为最大值  	for (int i = 1; i <= 4; i++)  		if (m[i] <= n) ans = min(ans, dp(n - m[i]) + 1);  	return ans;  }

记忆化搜索DP代码如下：

int dp(int n)  {  	if (n == 1 || n == 3 || n == 4 || n == 7)  return ans[n] = 1;  	if (ans[n]) return ans[n];  	ans[n] = INT_MAX;  	for (int i = 1; i <= 4; i++)  		if (m[i] <= n) ans[n] = min(ans[n], dp(n - m[i]) + 1);  	return ans[n];  }

(adsbygoogle = window.adsbygoogle || []).push({});