本文共 812 字，大约阅读时间需要 2 分钟。

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3

输出：-1

示例 3：

输入：coins = [1], amount = 0

输出：0

示例 4：

输入：coins = [1], amount = 1

输出：1

示例 5：

输入：coins = [1], amount = 2

输出：2

解题思路：动态规划解题思路，思考dp的含义以及动态转移方程

class Solution {
       public int coinChange(int[] coins, int amount) {
           // 动态规划解题 要考虑好动归数组的含义	    	int[] dp = new int[amount+1];	    	Arrays.fill(dp, amount+1);	    	dp[0] = 0;	    	// 对amount数组进行赋值	    	for(int i=1;i<=amount;i++) {
   	    		// 遍历硬币	    		for(int j=0;j
   
    =coins[j]) {
   	    				// 可兑换	    				// 状态转移方程	    				dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);	    			}	    		}	    	}	    	return dp[amount]>amount?-1:dp[amount];    }}
   

转载地址：http://xywdf.baihongyu.com/