A27081. 下面代码采用动态规划求解零钱兑换问题：给定n种硬币，第i种硬币的面值为 coins[i-1] ，目标金额为amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -1 。( )int coinchangeDPcomp(vector<int>&coins,int amt){ int n=coins.size(); int MAX = amt + 1; vecto…

下面代码采用动态规划求解零钱兑换问题：给定n种硬币，第i种硬币的面值为 coins[i-1] ，目标金额为amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -1 。(    )

int coinchangeDPcomp(vector<int>&coins,int amt){
	int n=coins.size();
	int MAX = amt + 1;

	vector<int>dp(amt +1，MAX);
	dp[e]= 0;

	for(int i=1;i<= n; i++){
		for(int a=1;a<= amt; a++){
			if(coins[i-1]>a)
				dp[a]= dp[a];
			else
				dp[a]=min(dp[a],dp[a-coins[i-1]]+ 1);
		}
	}
	return dp[amt]!=MX ?dp[amt]:-1;
}