LeetCode题组：第322题-零钱兑换

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

看到代码实现

//动态规划
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];
}