LCR 103. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
【思路】
dp 数组初始化：dp[0] = 0 是基础状态，其他位置初始化为 amount + 1，因为凑成金额 amount 最多需要 amount 枚 1 元硬币，amount + 1 是一个 “不可能” 的标记值。
状态转移公式：dp[i] = Math.min(dp[i], dp[i - coin] + 1) 是核心，意思是 “凑成金额 i 的最少硬币数，要么保持原来的值，要么是凑成 i - coin 的最少硬币数加 1 枚当前硬币，取更小的那个”。
public class CoinChange {public int coinChange(int[] coins, int amount) {// 定义dp数组，dp[i]表示凑成金额i所需的最少硬币数int[] dp = new int[amount + 1];// 初始化dp数组：除了dp[0]=0，其余初始化为amount+1（表示初始不可达）// 因为最多需要amount枚1元硬币，所以amount+1是一个不可能的大数for (int i = 1; i <= amount; i++) {dp[i] = amount + 1;}dp[0] = 0;// 遍历每个金额，从1到amountfor (int i = 1; i <= amount; i++) {// 遍历所有硬币面额for (int coin : coins) {// 如果当前硬币面额小于等于当前金额，才有可能更新dp[i]if (coin <= i) {// 状态转移：取「当前dp[i]」和「dp[i-coin]+1」的最小值dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}// 如果dp[amount]仍然大于amount，说明无法凑出该金额，返回-1；否则返回dp[amount]return dp[amount] > amount ? -1 : dp[amount];} }
【记 dp[0]=0 和 状态转移方程】
当i==coin时，也就是正好存在面值为i的硬币，dp[i-cion]+1=0+1——>dp[0]的用意