UVA674 Coin Change 简单的DP

刚开始一直都是RE，这道题目 题目的意思跟目的跟HDU2069是一样的，只是题目要求有了点变化，HDU2069是最多用100个钱币，这里呢 最多输入的 钱为7489，自然而然最多用到的钱币为7489个，所以一开始用了一样的方法，把数组开为8000*8000，可是一直RE，不知道为什么，也没有超内存，而且范围最多也不会超8000的，现在还不清楚，于是只能换思路了，仔细看看这道题目完全可以看作一个一维背包来做，意思就是给你一个容量为n的背包，让你用 体积有1，5，10，25，50五种不同的东西来填装，状态转移方程就很好推了  

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
//

ll dp[8000+5];
int value[6]={0,1,5,10,25,50};

void init() {
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	for(int i=1;i<=5;i++)
		for(int j=value[i];j<=7489;j++)
			dp[j] += dp[j-value[i]];
}

int main() {
	int n;
	init();
	while(cin>>n) {
		cout<<dp[n]<<endl;
	}
	return EXIT_SUCCESS;
}

UVA674 Coin Change 简单的DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/18367961