322.零钱兑换
1、题目
给你一个整数数组 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
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Related Topics
- 广度优先搜索
- 数组
- 动态规划
2、题目分析
动态规划通常用于求最优解。
解决套路可分为 2 步，①基于问题能定义出状态，②状态间具备动态规划的三个特性
①基于问题能定义出状态：问题是“凑成总金额所需的 最少的硬币个数”，而状态就可以定义为“每个金额所需的 最少的硬币个数”。因为这样，当流转到最终状态时，即可得到问题的答案。
②状态间具备动态规划的三个特性
- 子问题重复且策略重复：
子问题重复：每个状态就是一个重复的子问题，都是问该金额下所需的 最少的硬币个数
策略重复：策略都是判断该金额减去各硬币后的金额是否已被求得硬币个数，若是，则在此硬币个数上 + 1 - 最优子结构：
该金额下所需的 最少的硬币个数。等于该金额减去各硬币后的金额所需的 最少的硬币个数 + 1 - 无后效性
无需考虑更前阶段对本阶段的影响：该金额只与减去各硬币后的金额所处的状态有关联，而无需关注该金额减去各硬币后的金额如何一步步推导而来。
后续阶段对本阶段不会产生影响：该金额所需的 最少的硬币个数 被确定后，不会被后续金额的决策所影响
3、解题步骤
1、将凑齐每个金额对应的最少硬币数初始化为无穷大，意味着未计算出凑齐每个金额所需最少的硬币数，简化dp代码的编写
2、动态规划凑齐1~amount，各需要的最少硬币数
3、明确i元在本次无法凑齐的2个原因，并记录凑齐i元的最少硬币数
4、dp[amount] 表示凑齐 amount 所需的最少硬币数，若值为无穷大，意味着不可凑齐 返回-1，否则返回 dp[amount]
4、复杂度最优解代码示例
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 1、将凑齐每个金额对应的最少硬币数初始化为无穷大，意味着未计算出凑齐每个金额所需最少的硬币数，简化dp代码的编写
Arrays.fill(dp, Integer.MAX_VALUE);
// 凑齐0元，无需硬币
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
// 2、动态规划凑齐1~amount，各需要的最少硬币数
// 先初始化凑齐i元的最少硬币数为无穷大。
int iMin = Integer.MAX_VALUE;
for (int coin : coins) {
if (i - coin < 0 || (dp[i - coin] == Integer.MAX_VALUE)) {
// 3、i元在本次无法凑齐的2个原因：
// a. i - coin < 0，意味着单个硬币金额 > 所需凑齐金额，故本硬币无法用来凑齐该金额
// b. dp[i - coin] == Integer.MAX_VALUE，意味着本金额-本硬币金额前的状态 未可达，继而无法借助前面的状态转移到当前状态。
continue;
}
// c、记录凑齐i元的最少硬币数
iMin = Math.min(iMin, dp[i - coin] + 1);
}
dp[i] = iMin;
}
// 4、dp[amount] 表示凑齐 amount 所需的最少硬币数，若值为无穷大，意味着不可凑齐 返回-1，否则返回 dp[amount]
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
5、抽象与扩展
通用动态规划的解法，见标题二
