本文主要是介绍第四十五天 | 322.零钱兑换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：322.零钱兑换
尝试解答：
1.确定dp[j]含义：装满容量为j的背包所需要放的硬币个数为dp[j];
2.动态转移方程：dp[j] = dp[j - coins[i]] + 1;
3.遍历顺序：本题应该为组合类题目，不考虑装入的顺序，只在乎硬币个数
所以先物品后背包，背包容量从小到大。（错）
4.初始化：dp[0] = 1,其余均初始换为0
5.打印dp
代码实现如下，有漏洞，执行不对：
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, 0);dp[0] = 1;int result = INT_MAX;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){// dp[j] = dp[j - coins[i]] + 1;// result = min(dp[j], result);if(j == amount){result = min(dp[j], result);}}}return result;}
};正确思路：
1.确定dp[j]含义：装满容量为j的背包所需要最少放的硬币个数为dp[j];
2.动态转移方程：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
本轮要放的物品重量为coins[i]，所以背包必须腾出coins[i]这么大的容量留给coins[i]，所以之前背包装的重量必须是dp[j - coins[i]]。装了coins[i]后，一共装了dp[j - coins[i]] + 1块硬币，与不装coins[i] 的情况比大小，取其小，得到本轮循环的最优解，就是本次的最少个数。
3.初始化：
本题初始化比较取巧，之前不管是排列还是组合，dp[0]都初始化为了1，但这到题从测试样例中可以看出，dp[0] = 0。
其他位置的值如何进行初始化？从本质入手，因为是取其小，必须将他们初始化为INT_MAX，才可以保证在二维数组的第一行可以成功更改值，不会被原来初始化的值覆盖（解释这一点时我习惯从二维数组的角度出发）。
其实道理和其他题目中，初始化为0的道理是一样的，其他题目如果是取其大max，则初始化为0，只要没有负数的情况，就可以保证能够更新值，不会被覆盖。
4.遍历顺序：
本题对遍历顺序无要求。
首先要分清楚题目类型：本题是求装满背包的最少个数，不是求装满背包有多少种方法，
所以这道题和排列组合无关，对遍历顺序无特殊要求。
只有题目问“方法数”时，才考虑排列还是组合，先背包还是先物品。
5.打印dp
代码如下：
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){ //遍历物品for(int j = coins[i]; j <= amount; j++){ //遍历背包if(dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};对于返回-1的条件不是很理解。
循环里的判断条件：如果dp[j - coins[i]] != INT_MAX，那么是不可能通过目前遍历到的物品将背包装满的。
返回值时进行的判断：如果dp[amount] == INT_MAX，那么不可能将背包装满。
这篇关于第四十五天 | 322.零钱兑换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
