【题解】找零钱—动态规划
给定一些人民币的面额，数量不限，要求找出金额为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];
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。