首页 > 代码库 > 初级硬币最大最小问题递推法

初级硬币最大最小问题递推法

static int* Min;static int* Max;void LeastCoin2(int* Value, int Len, int *d, int Goal) {	for(int i = 1; i <= Goal; i++)	{		for(int j = 0; j < Len; j++)		{			if(i >= Value[j])             			{                                   int distance = i - Value[j];				int temp1 = Min[distance] + 1;  				int temp2 = Max[distance] + 1;				Min[i] = Min[i] < temp1 ? Min[i] : temp1;				Max[i] = Max[i] > temp2 ? Max[i] : temp2;			}	}		}}void WLeastCoin2(int* Value, int Len, int Goal)  {	int* d = new int [Goal+1];	if(d == NULL)	{	    printf("malloc fail \n");	}	memset(d, -1, sizeof(int)*(Goal+1));	d[0] = 0;	printf("goal: %d\n", Goal);	Min = new int [Goal+1];	for(int i = 0; i < Goal+1; i++)	{		Min[i] = 1<<10; //不能太大,防止溢出	}	Min[0] = 0;	Max = new int [Goal+1];	memset(Max, 0, sizeof(int)*(Goal+1));	LeastCoin2(Value, Len, d, Goal);	for(int i = 0; i <= Goal; i++)	{		printf("%d ", Min[i]);//Min[Goal]   Min	}	printf("\n");	for(int i = 0; i <= Goal; i++)	{		printf("%d ", Max[i]);//Max[Goal]  Max	}	printf("\n");}

  

初级硬币最大最小问题递推法