力扣 | 322. 零钱兑换

这里使用动态规划，代码简洁更易理解

package _322;import java.util.Arrays;public class Problem_322_CoinChange {public int coinChange(int [] conins,int amount){//1. 状态定义，dp[i]表示凑齐金额为i的时候的最小硬币数量int dp [] = new int[amount + 1];//2. 状态初始化，因为比较的是最小值，所以不可能比总金额数更大Arrays.fill(dp,amount + 1);//或者初始化为Math.MAXVALUE;//凑齐总金额数为 0 的时候的硬币数量就是不选硬币dp[0] = 0;//3. 状态转移for (int i = 0; i < conins.length; i++) {for (int c = conins[i]; c <= amount; c++) {dp[c] = Math.min(dp[c],1 + dp[c - conins[i]]);}}//4. 返回最终需要的状态值return dp[amount] == amount + 1 ? -1 : dp[amount];}
}