硬币组合问题

//硬币的找零问题，给定一个数值，求使得最少的硬币数组合成所要的数值
int CoinChange(vector<int> coins,int len,int sum)
{
	vector<int> dp(sum+1,sum+1);
	dp[0]=0;//设定为0
	for(int i=1;i<=sum;i++)
	{
		for(int j=0;j<len;j++)
		{
			if(coins[j]<=i)
				dp[i]=min(dp[i],dp[i-coins[j]]+1);
		}
	}
	return dp[sum]>sum?-1:dp[sum];
}
//dp[i][j]=sum(dp[i-1][j-k*coins[i-1]]),k=0,1,2,...j/coins[i-1]
int CoinsCombination(vector<int> &a,int len,int sum)
{
	vector<vector<int>> dp(len+1);
	vector<int> vec(sum+1,0);
	for(int i=0;i<=len;i++)
		dp[i]=vec;
	for(int i=0;i<=len;i++)
		dp[i][0]=1;//每一种硬币组合成数值0的方法为1
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=sum;j++)
		{
			dp[i][j]=0;
			for(int k=0;k<=j/a[i-1];k++)
				dp[i][j]+=dp[i-1][j-k*a[i-1]];
		}
	}
	return dp[len][sum];
}