题目链接：

链接

题目描述：

思路：

类似于“完全平方数”

设金额$i$所需的最少个数是$dp[i]$
则： d p [ i ] = m i n { d p [ i ] , d p [ i − c o i n s [ j ] ] + 1 } dp[i] = min\{ dp[i],dp[i-coins[j]] + 1 \} dp[i]=min{dp[i],dp[i−coins[j]]+1}

这里 初始个数 设置为 amount+1，是为了确保在 结果应该是-1 的时候，dp[amount] > amount 成立

实现代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i = 1; i <= amount; i++){
            int min = amount+1;
            for(int j = 0; j < coins.length; j++){
                if(coins[j] <= i){
                    min = Math.min(min,dp[i - coins[j]] + 1);
                }
            }
            dp[i] = min;
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}