硬币问题之记忆化搜索-动态规划 By ACReaper

#include <stdio.h>
#include <string.h>
#define MAXLEN 10001
#define COINLEN 101
int V[COINLEN];
int vis[MAXLEN];
int d[MAXLEN];
int n;
int dpmax(int s);
int dpmin(int s);
int main(){
	int s;
	while(scanf("%d%d",&n,&s) != EOF){
		for(int i = 1; i <= n ; i++)
			scanf("%d",&V[i]);
		memset(vis,0,sizeof(vis));
		printf("%d",dpmax(s));
		memset(vis,0,sizeof(vis));
		printf(" %d\n",dpmin(s));
		
	}
	return 0;
}

int dpmax(int s){
	if(s == 0)
	 	return 0;
	if(vis[s]) 
		return d[s];
	vis[s] = 1;//记住 
	d[s] = -1 << 30;
	for(int i = 1; i <= n; i++){
		if(s >= V[i])
			d[s] >?= dpmax(s - V[i]) + 1;
	}
	return d[s];
}
int dpmin(int s){
	if(s == 0)
	 	return 0;
	if(vis[s])
		return d[s];
	vis[s] = 1;//记住 
	d[s] = 1 << 30;
	for(int i = 1; i <= n; i++){
		if(s >= V[i])
			d[s] <?= dpmin(s - V[i]) + 1;
	}
	return d[s];
}

转载于:https://www.cnblogs.com/sixcoder/archive/2013/04/12/3826015.html