322. 零钱兑换

题目描述：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

和 518.零钱兑换II 区别在于本题返回凑成总金额所需的最少的硬币个数，而 518.零钱兑换II 返回可以凑成总金额的硬币组合数

区别在于：

1. 递推公式不同

本题：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);

518.零钱兑换II：dp[j] += dp[j - coins[i]]; // 求总和

1. 初始化不同

本题 dp[0] = 0; 然后其他元素初始值设为正无穷 518.零钱兑换II 中 dp[0] = 1;

1. 遍历顺序要求不同

本题：求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

518.零钱兑换II求得是组合数，一定要外层for循环遍历物品，内层for遍历背包。

如果dp[j - coins[i]]是初始值则跳过，if (dp[j - coins[i]] == INT_MAX) continue;

dp五步曲：

1. dp[i] 表示总金额为 i 所需的最少的硬币个数
2. 递推公式：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
3. 初始化

dp[0]=0;

其他的初始化为正无穷

1. 遍历顺序

此时，内外层顺序无关完全背包物品可以重复使用，所以内层正序（01背包中一维dp，内层必须倒序，保证只用一次）

1. 打印dp

如果dp[j - coins[i]]是初始值则跳过, if (dp[j - coins[i]] == INT_MAX) continue;

279. 完全平方数(完全背包)

题目描述：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、 4、9 和 16 都是完全平方数，而 3 和 11 不是。