零钱兑换、、

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

我们采用自下而上的方式进行思考。仍定义

F(i)

为组成金额

i

所需最少的硬币数量，假设在计算

F(i)

之前，我们已经计算出

F(0)-F(i-1)

的答案。 则 F(i)F(i)F(i) 对应的转移方程应为

F(i)=\min_{j=0 \ldots n-1}{F(i -c_j)} + 1

其中

c_j

代表的是第 jjj 枚硬币的面值，即我们枚举最后一枚硬币面额是

c_j

，那么需要从

i-c_j

这个金额的状态

F(i-c_j)

转移过来，再算上枚举的这枚硬币数量

1

的贡献，由于要硬币数量最少，所以

F(i)

为前面能转移过来的状态的最小值加上枚举的硬币数量

1

。

例子1：假设

coins = [1, 2, 5], amount = 11 则，当 i==0时无法用硬币组成，为 0 。当 i<0时，忽略 F(i)

F(i)    最小硬币数量 F(0)    0 //金额为0不能由硬币组成 F(1)    1 //F(1)=min(F(1−1),F(1−2),F(1−5))+1=1 F(2)    1 //F(2)=min(F(2−1),F(2−2),F(2−5))+1=1 F(3)    2 //F(3)=min(F(3−1),F(3−2),F(3−5))+1=2 F(4)    2 //F(4)=min(F(4−1),F(4−2),F(4−5))+1=2 ...    ... F(11)    3 //F(11)=min(F(11−1),F(11−2),F(11−5))+1=3 我们可以看到问题的答案是通过子问题的最优解得到的。     例子2：假设

coins = [1, 2, 3], amount = 6

在上图中，可以看到：

\begin{aligned} F(3) &= \min({F(3- c_1), F(3-c_2), F(3-c_3)}) + 1 \\ &= \min({F(3- 1), F(3-2), F(3-3)}) + 1 \\ &= \min({F(2), F(1), F(0)}) + 1 \\ &= \min({1, 1, 0}) + 1 \\ &= 1 \end{aligned}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

复杂度分析

时间复杂度：O(Sn)，其中S是金额，n是面额数。我们一共需要计算O(S)个状态，S为题目所给的总金额。对于每个状态，每次需要枚举n个面额来转移状态，所以一共需要O(Sn)的时间复杂度。 空间复杂度：O(S)。数组

\textit{dp}

需要开长度为总金额S的空间。