思路动态规划。dp[i] 表示凑成金额 i 所需的最少硬币数。初始化 dp[0] 0其他为一个不可能的大值 amount 1。遍历金额 1 ~ amount对每种硬币尝试更新dp[i]Math.min(dp[i],dp[i-coin]1);最后如果 dp[amount] amount说明无法凑成返回 -1。Java 实现importjava.util.Arrays;classSolution{publicintcoinChange(int[]coins,intamount){intmaxamount1;int[]dpnewint[amount1];Arrays.fill(dp,max);dp[0]0;for(inti1;iamount;i){for(intcoin:coins){if(coini){dp[i]Math.min(dp[i],dp[i-coin]1);}}}returndp[amount]amount?-1:dp[amount];}}复杂度· 时间复杂度O(amount * coins.length)· 空间复杂度O(amount)示例coinChange(newint[]{1,2,5},11);// 返回 3即 5 5 1coinChange(newint[]{2},3);// 返回 -1coinChange(newint[]{1},0);// 返回 0