编辑代码

#include<stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>

/*
Leetcode-322-零钱兑换  题目描述
给定不同面额的硬币 coins 和一个总金额 amount
编写一个函数来计算可以凑成总金额所需的最少的硬币个数
如果没有任何一种硬币组合能组成总金额，返回 -1
*/

int coinChange(std::vector<int> coins, int amount) {
	//因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），
	//所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

	//定义(amount + 1)个整型元素的向量,且给每个元素的初值为(amount + 1)
	std::vector <int> dp(amount + 1, amount + 1);    // dp(i) 为组成金额 i 所需的最少的硬币数量
	//std::vector <int> dp(amount, amount);
	dp[0] = 0;

	for (int i = 1; i <= amount; i++)   // 金额i
	{
		for (int j = 0; j < (int)coins.size(); j++)   // 第j枚硬币
		{
			if (coins[j] <= i)     // coins[j]​ 代表的是第 j 枚硬币的面值
				dp[i] = std::min(dp[i], dp[i - coins[j]] + 1);
				//dp[i] = std::min(dp[i - coins[j]] + 1);
		}
	}
	return dp[amount] > amount ? -1 : dp[amount];
}

int main(){
	int result = coinChange({1,2,5}, 11);  // 即分别有面值为1、2、5的硬币，要求凑齐的总金额为11， 输出结果为3
	// int result = coinChange({ 1,2,3 }, 6);  // 输出结果为2
	std::cout << result << std::endl;
	return 0;
}