LeetCode 322 零钱兑换

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

示例 1：

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

示例 2：

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

示例 3：

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

思路：

确定dp数组以及下标的含义
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，
那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
确定遍历顺序
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在代码中，if(dp[j - coins[i]] != INT_MAX)表示如果如果dp[j - coins[i]]是初始值则跳过
说明没有可以凑成j-conis[i]的结果
最后先判断dp[amount]是否为初始化的最大值，如果是，说明没有结果

class Solution {
public:int track(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], dp[j - coins[i]] + 1);}}}return dp[amount];}
};int main() {vector<int> coins = { 1,2,5 };int amount = 11;Solution ss;cout<<ss.track(coins,amount)<<endl;return 0;
}