第四十五天 | 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，那么不可能将背包装满。