class Solution {
    /*
    自底向上的动态规划
    */
    public int coinChange(int[] coins, int amount) {
        if(coins.length==0) return -1;
        int[] memo=new int[amount+1];
        Arrays.fill(memo,amount+1);//初始化为一个不可能到达的数量amount+1
        memo[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(i>=coins[j]){
                    memo[i]=Math.min(memo[i],memo[i-coins[j]]+1);
                    //memo[i]的两种情况：包含coins[j],不包含conis[j]
                }
            }
        }
        if(memo[amount]==amount+1)//没结果
            return -1;
        else
            return memo[amount];
    }
}

复杂度

coins长度为m,amount为n
时间复杂度O(mn)：对1…amount取值，需要枚举coins。
空间复杂度O(n)：dp数组占用的空间

结果