LeetCode-322. 零钱兑换

LeetCode-322. 零钱兑换 (中等)

题目地址：https://leetcode-cn.com/problems/coin-change/

文章目录

• LeetCode-322. 零钱兑换 (中等)
• 1. 题目描述及示例
• • • 示例一：
    • 示例二：
    • 示例三：
• 2. 题解和代码实现
• • • 2.1 初始化
    • 2.2 状态转移方程
    • 代码实现（C++ 2022-4-28）
• 3. 总结

1. 题目描述及示例

      给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
      计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
      你可以认为每种硬币的数量是无限的。

示例一：

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释：11 = 5 + 5 + 1

示例二：

输入: coins = [2], amount = 3
输出: -1

示例三：

输入: coins = [1], amount = 0
输出: 0

2. 题解和代码实现

      针对最少硬币数 ，我们可以采用动态规划的方法进行解决。在进行解题时，很容易发现，动态规划的难处在于不容易找到合适的状态转移方程。针对此题，我们的状态转移方程，首先考虑的是利用整数数组coins中的数据作为dp，但是对于总数，每次添加一种类型的硬币，发现这两个状态之间没有什么可以遵循的必然联系，所以无法进行获得动态规划。
      换一种思路，如果我们利用总金额来做dp，状态之间的关系是：可以通过不同的硬币来进行获得，即：dp[i] = min{dp[i-coins[j]]}+1。

2.1 初始化

      针对总金额为0，我们有dp[0] = 0，所以我们进行定义amount+1的空间的dp数组。

	int n = amount + 1;
	vector<int> dp(n,0);

2.2 状态转移方程

      已经了解到 dp[i] = min{dp[i-coins[j]]}+1。

	int temp = amount + 1; //针对总金额所有的硬币个数，不会超过 amount + 1个
	for(int j = 0;j < coins.size(); j++){
		if(i>=coins[j]){ //针对无法进行利用硬币表示的总金额我们不去考虑
			temp = min(temp,dp[i-coins[j]);
		}
	}
	dp[i] = temp+1;

代码实现（C++ 2022-4-28）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
    	int n = amount + 1;
    	// 在这里，我们使用dp[amount+1] 来进行存放，组成这个总价所需的硬币数目
    	// 我们的状态转移方程是什么呢？
    	// 那么肯定是 min{dp[i-coins[j]}+1
    	vector<int> dp(n,0);
    	for(int i = 1;i < n; i++){
    		int temp = n;
    		for(int j = 0;j < coins.size();j++){
    			if(i>=coins[j]){
    				temp = min(temp,dp[i-coins[j]]);
    			}
    		}
    		dp[i] = temp + 1;
    	}
    	// 判断最后的输出值是否不存在，如果比amount还大，那么代表无法组成
    	// 
    	return dp[amount] > amount ?-1 : dp[amount];
    }
};

3. 总结

      难点在于找到合适的状态转移方程。