本文主要是介绍uva674 - Coin Change(硬币找零)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
开始的时候用的是dfs+剪枝，很快的就TLE了
后来想到dp的记忆化搜索。于是开始苦苦的寻求状态方程，经过一遍又一遍的模拟，我找到了一个规律，
就是每增加一种硬币就更新一次状态，但是所得规律不对，连样例都过不了，后来继续找。。。。
再后来，我就没出息的搜了结题报告了，，
等到我彻底理解了，才写的代码。
也勉强的算上转化为自己的东西了吧
代码如下：
#include <cstdio>
#include <cstring>
#define M 7500
int ans, v[5] = {1,5,10,25,50}, dp[M];
int main ()
{int n;dp[0] = 1;for(int i = 0; i < 5; i++)for(int j = 0; j < M; j++) if(j>=v[i])dp[j]+=dp[j-v[i]];while(scanf("%d",&n)!=EOF)printf("%d\n",dp[n]);return 0;
}
这篇关于uva674 - Coin Change(硬币找零)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
