class Solution {
    private int dp[];//构建一个一维数组来存储次数
    
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount == 0) {
            return 0;
        }
        dp=new int[amount+1];
        Arrays.sort(coins);
        for(int i=0;i<coins.length;++i) {
            for(int j=1;j<=amount;++j) {
                if(j==coins[i]) {
                    dp[j]=1;
                }
                if(j>coins[i]) {
                    if(dp[j-coins[i]]!=0) {
                        if(dp[j]==0) {
                            dp[j]=dp[j-coins[i]]+1;
                        }
                        else
                            dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
                    }
                }
            }
        }
        return dp[amount]==0?-1:dp[amount];
    }
}