给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

算法1（暴力递归）

时间复杂度：\(O(kn^k)\)
分析状态转移方程：

1. 确定base case。即目标金额为0时返回0
2. 确定状态，也就是原问题和子问题中会变化的量。本题中即为目标金额，随着每一次选择不同面值的硬币而递减，逐渐向base case靠近。
3. 确定选择，也就是导致状态发生变化的行为。本题中即为不同面值的硬币可供选择，所以所有硬币的面值即为选择。
4. 明确dp函数/数组的定义。本题的状态为目标金额的值，题目要求计算出达成目标的最少硬币个数。所以dp函数的定义为输入一个目标金额n，返回需要的最少硬币个数

伪代码：

int coinChange(int coins[], int amount) {
	return dp(coins, amount);
}

int dp(int coins, int amount) {
	for (auto coin : coins) {
		res = min(res, 1 + dp(coins, amount - coin))
	}
}

目标金额为0时，即零钱兑换成功，返回1，目标金额为负时，即兑换失败，返回-1。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        return dp(coins, amount);
    }

    int dp(vector<int>& coins, int amount) {
        //base case
        if (amount == 0) return 0;
        if (amount < 0) return -1; //兑换失败

        int res = amount + 1;
        for (auto coin : coins) {
            //计算子问题
            int subProblem = dp(coins, amount - coin);
            //若兑换失败则跳过
            if (subProblem == -1) continue; 
            //选择子问题最优解
            res = min(res, subProblem + 1);
        }
        return (res == amount + 1) ? -1 : res;
    }
};

很可惜，这种方法会超时，我们要采取一些优化措施。

算法2（带备忘录的递归）

分析本题的递归树，我们不难发现会有重复的计算问题，我们可以通过备忘录来减少子问题数目，消除子问题的冗余。子问题总数不超过金额数n，所以子问题个数是\(O(n)\)，处理每一个子问题时有一个for循环，时间复杂度为\(O(k)\)，所以整个算法的时间复杂度为\(O(kn)\)。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int memo[amount + 1];
        for (int i = 0; i < amount + 1; i ++ ) memo[i] = -666;
        return dp(coins, amount, memo);
    }

    int dp(vector<int>& coins, int amount, int memo[]) {
        //base case
        if (amount == 0) return 0;
        if (amount < 0) return -1; //兑换失败

        if (memo[amount] != -666) {
            return memo[amount];
        }

        int res = amount + 1;
        for (auto coin : coins) {
            //计算子问题
            int subProblem = dp(coins, amount - coin, memo);
            //若兑换失败则跳过
            if (subProblem == -1) continue; 
            //选择子问题最优解
            res = min(res, subProblem + 1);
        }

        memo[amount] = (res == amount + 1) ? -1 : res;

        return memo[amount];
    }
};

算法3（dp数组的迭代解法）

时间复杂度：\(O(kn)\)
算法2中我们自顶向下使用备忘录解决了冗余问题，同时我们也可以通过自底向上使用dp table消除子问题，此时dp函数体现在函数参数，dp数组体现在数组索引。
dp数组定义：dp[i]代表兑换金额为i时最少需要dp[i]枚硬币。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);

        dp[0] = 0;
        for (int i = 0; i <= amount; i ++ ) {
            for (auto coin : coins) {
                if (i - coin < 0) continue;
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
};