力扣 | 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];
    }
}