1.题目
难度：中
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 5 1
示例 2:
输入: coins = [2], amount = 3 输出: -1
说明：你可以认为每种硬币的数量是无限的。
2.我的解答
思路：
- 看题目的问法，只问最优值是多少，没有要我们求最优解，可以通过
动态规划来解决这个问题； - 最优子结构其实比较明显，根据示例 1：
输入: coins = [1, 2, 5], amount = 11
凑成面值为 11 的最小硬币数可以由以下 3 者的最小值得到：
1、凑成面值为 10 的最小硬币数 面值为 1的这一枚硬币；
2、凑成面值为 9 的最小硬币数 面值为 2 的这一枚硬币；
3、凑成面值为 6 的最小硬币数 面值为 5 的这一枚硬币；
即：dp[11] = min (dp[10] 1, dp[9] 1, dp[6] 1)。
可以直接把题目的问法设计成状态。
第 1 步：定义「状态」
dp[i]：凑齐总价值i需要的最少硬币数，状态就是问的问题。
第 2 步：写出「状态转移方程」
根据对具体例子的分析：
dp[amount] = min(1 dp[amount - coin[i]]) for i in [0, len - 1] if coin[i] <= amount
看到代码实现
代码语言：javascript复制//动态规划
int coinChange(int* coins, int coinsSize, int amount){
int i,j;
int *dp=(int *)malloc(sizeof(int)*(amount 1));//dp[i]代表i金额最小的
memset(dp,-1,sizeof(int)*(amount 1));//初始化
//将硬币值的大小当做dp数组的下标
for(i=0;i<coinsSize&&coins[i]<=amount;i ) dp[coins[i]]=1;
dp[0]=0;
for(i=0;i<=amount;i )//状态转移方程
{
int number=amount 1;
//逐个比较i-coins[j]所需的最小硬币数
for(j=0;j<coinsSize;j )
{
//如果硬币可用
if(i-coins[j]>=0&&dp[i-coins[j]]!=-1)
number=dp[i-coins[j]]<number ? dp[i-coins[j]] 1 : number;
}
if(number!=amount 1) dp[i]=number;
}
return dp[amount];
}
