leetcode322题解-526互联

今天来解析一下一道中等的leetcode题，题目如下:

给你一个整数数组 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

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

这其实就是一个背包问题，而背包问题一般有两种解法

先遍历物品，在填充背包
先遍历背包，在用物品填充背包

这里我用的是先物品在背包代码如下：

    int coinChange(vector<int>& coins, int amount) {
        
        vector<int> dp(amount+1,INT_MAX);
        //i表示金额
        //dp[i]表示凑成i金额需要的最少数量

        dp[0]=0;
        for(int i=0;i<coins.size();i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {   
                if(dp[j-coins[i]]!=INT_MAX)
                {
                    // 前面dp值在有计算过的基础上才能转移
                    //dp[j]不装，dp[j-coins[i]]+1装
                    dp[j]=min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }

        return  dp[amount] == INT_MAX ? -1 : dp[amount];
    }

动态规划一般有三个步骤，dp定义、初始化、状态转移。

1.dp定义：dp[i]定义为遍历到i（代表金额）时，所选的硬币能凑成目标金额的最少数量。

2.dp初始化：我们把dp数组设为最大值，方便后续更新。

3.状态转移：dp[j]=min(dp[j],dp[j-coins[i]]+1);这一步也是最难的，需要多做才能想到。