算法：零钱兑换

public int CoinChange(int[] coins, int amount)
{
	// 如果输入的金额小于等于0，返回0
	if (amount <= 0) return 0;

	// 设置初始值为 amount + 1，实际不存在这种情况的，最坏的情况是 amount 
	var minCount = amount + 1;

	for (int i = 0; i < coins.Length; i++)
	{
		Cal(amount, coins, coins[i], new List<int>(), ref minCount);
	}
	return minCount == amount + 1 ? -1 : minCount;
}

public void Cal(int amount, int[] coins, int coin, List<int> curCoins, ref int minCount)
{
	// 剩余金额-使用的硬币金额， 得到新的剩余金额
	var leftAmount = amount - coin;

	// 如果等于0，说明找到了一组满足的组合
	if (leftAmount == 0)
	{
		curCoins.Add(coin);

		// 如果当前组使用的硬币数量小于当前最小组合的硬币数量，重置最小值
		if (curCoins.Count < minCount)
		{
			minCount = curCoins.Count;
		}
	}
	// 如果剩余金额大于0，说明还继续获取新的硬币加入集合
	else if (leftAmount > 0)
	{
		// 如果当前组的总硬币数量已经大于当前最小组合的硬币数量，就不需要在往下找了
		if (curCoins.Count >= minCount)
		{
			return;
		}

		// 继续下一次
		for (int i = 0; i < coins.Length; i++)
		{
			var newCoins = new List<int>(curCoins);
			newCoins.Add(coin);
			Cal(leftAmount, coins, coins[i], newCoins, ref minCount);
		}
	}
}

public int CoinChange(int[] coins, int amount)
{
	var dp = new int[amount + 1];
	// dp[0] 为 0，其他默认为 amount + 1（实际是不可能的），为了方便取对比结果中的最小值
	for (int i = 1; i < dp.Length; i++)
	{
		dp[i] = amount + 1;
	}

	// 计算 1~amount 每项 dp[i] 的值
	for (int i = 1; i <= amount; i++)
	{
		for (int j = 0; j < coins.Length; j++)
		{
			// 如果i能使用存在的面额来组合，得到每种面值组合后的最小值
			if (coins[j] <= i)
			{
				dp[i] = Math.Min(dp[i], dp[i - coins[j]] + 1);
			}
		}
	}

	// 如果 dp[amount] 是 amount + 1 ，代表没找到组合结果，否则返回组合成 amount 需要的最少硬币数 dp[amount]
	return dp[amount] > amount ? -1 : dp[amount];
}