题目描述

给定不同面额的硬币 coins 和一个总金额amount
求凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。

样例

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

输入: coins = [2], amount = 3
输出: -1

输入: coins = [2], amount = 0
输出: 0

算法1

朴素法 [leetcode上超时]

完全背包的变形，价值即为1

背包
集合 ： 用前i个物品 ，装进体积为j 的所有方案的集合 f[i][j]
属性 ： 所选方案中物品价值的最大值`最小值计算 | 集合的划分 ：第i个物品选择次数来划分
0 1 ： 每个物品只能选择0或者 1次
完全 ： 每个物品可以选择无数次，但是不能超过背包的体积

复杂度

时间 ： 两重循环 O(nm)
空间 ： 二维向量 O(n*m)

C++ 代码

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

        for(int i = 0; i <= n; i++) dp[i][0] = 0;  // 存在硬币数 凑0元的话 硬币数一定为0
        // 不存在硬币 去凑 肯定凑不出来    所以初值不用更改
        // for(int i = 0; i <= amount; i++) dp[0][i] = 0;


        for(int i = 1; i <= n ;i++)
        {
            for(int j = 1; j <= amount; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1])
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i-1]] + 1); 
                cout << dp[i][j] << " " ;
            }


        }           

        return dp[n][amount] <= amount ? dp[n][amount] : -1;

    }
};

算法2

(优化空间)

复杂度

时间 ： 两重循环 O(nm)

空间 ： 一维向量 O(m+1)

C++ 代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp (amount + 1, amount + 1);
        dp[0] = 0;

        for(int i = 1; i <= n ;i++)
            for(int j = coins[i - 1]; j <= amount; j++)
                dp[j] = min(dp[j], dp[j - coins[i-1]] + 1); 

        return dp[amount] <= amount ? dp[amount] : -1;

    }
};