一、题目描述
原题链接
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
二、题目分析
这道题和爬楼梯有相同之处，决策换成不同硬币的面额，爬到楼顶换成了凑成硬币总金额。假设有n枚硬币凑成总金额amount，那么必定满足第n-1枚硬币的总金额 = amount-第n枚硬币的面额，因此我们把凑amount至少所用硬币数转化成了凑amount-第n枚硬币的面额至少所用硬币数。我们可以用一维数组来存储硬币的金额和个数，（当然也可用二维数组）。
求解
- 状态变量：dp[n]表示当前所凑硬币总金额为n，至少所需的硬币数
状态转移方程：当n = 0 时，dp（n）=0.
- 当n<0时，dp（n）=-1.
- 当n>0时，dp（n）={ min（dp（n-coin）+1）| coin∈coins }
因此 状态转移方程为:
**dp[i] = Math.min(dp[i], dp[i - coin] + 1);**i为硬币的总金额，dp[i] 为最少所用的硬币数
coin为可供选择的硬币面额
- 初始条件： dp（0）= 0 当总金额为0时，所需硬币数为0
- 边界条件： i-coin<0 表示不能凑成所给的总金额amount
三、代码实现
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
//将数组所有数置为最大值 作用：保证可以用给定面额硬币拼凑的总金额数是有意义的
Arrays.fill(dp, Integer.MAX_VALUE);
//定义初始条件
dp[0] = 0;
//当amount为0时，所需硬币数为0
if (amount == 0) {
return 0;
}
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
//如果可以凑成差值
if (dp[i - coin] != Integer.MAX_VALUE) {
//状态转移方程 可以凑成差值
//在原有的基础上 和 用新面额硬币替换原来的金额并更新硬币个数
// 两者之中选出最小的硬币个数
dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
}
}
}
//如果dp[amount]=Integer.MAX_VALUE
//那么说明用任意所给硬币面额随意拼凑都不能满足amount总金额
return dp[amount] < Integer.MAX_VALUE ? dp[amount] : -1;
}
}``` 
