https://leetcode-cn.com/problems/coin-change/
首先常见的贪心算法不合适，因为每个币值是任意大小的，不能先用最大币的组合，再用较小，比如[7,5,1]，amount是10，按照贪心算法，应该是4个币(7,1,1,1)，但是(5,5)两个币其实就能组成。

我的方法一：动态规划

步骤

1. 确认状态
   1.1 最后一步：加入最后一个硬币组成amount
   1.2 子问题：最后一个硬币是是coins中的一个，那么去除最后这一个，剩余总额需要最少的硬币数+1，就是amount的最少硬币数
2. 转移方程
   f(n) = min(f(n-coins[i]))
3. 初始和边界条件
   f(0) = 0
   f(coins[i]) = 1
   如果最后计算得到的值是0，那么返回-1，表示无法表示出来
4. 计算顺序
   f(1) f(2) f(n)

复杂度

时间复杂度：O(N)，最多计算N个值的结果
空间复杂度：O(N)，需要将amount个值的结果都保存下来

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(coins.size() == 0){
            return -1;
        }
        if(amount == 0){
            return 0;
        }

        vector<int> f(amount+1, -1);
        for(auto& coin : coins){
            if(coin < f.size()){
                f[coin] = 1;
            }
        }

        int sub = 0;
        for(int i=1; i<=amount; i++){
            for(int c = 0; c<coins.size(); c++){
                sub = i - coins[c];
                if(sub >= 0){
                    if(f[sub]>=0){
                        if(f[i] == -1 || f[i] > f[sub] + 1){
                            f[i] = f[sub] + 1;
                        }
                    }
                }
            }
            //cout<<"f["<<i<<"] = "<<f[i]<<endl;
        }

        return f[amount];
    }
};

其他更好的方法

官方更简洁的写法

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];
    }
};

BFS广度优先搜索

很巧妙的思路
https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-shi-yong-wan-quan-bei-bao-wen-ti-/