322.零钱兑换 (Medium)*

题目描述*

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

示例*

输入: coins = [1, 2, 5], amount = 11

输出: 3

解释: 11 = 5 + 5 + 1

说明*

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

代码*

经典的动态规划，自下而上或自顶向下。

但是这些的速度都不太行，题解里看到有带哥用贪心加 dfs。思路如下：

贪心：想要硬币最少，肯定是优先用大面值硬币，所以先对 coins 排序；先用大硬币，当总额超过时就需要递归较小的硬币。
可以用乘法替代一个个减，k = amount / coins[i]; amount -= k * coins[i]; cnt += k; 如果因为丢多了找不到总额就慢慢减。
最先找到的并不是最优解，所以还是需要把所有情况递归完。
剪枝，贪心最然不是最优解，但是还是有用的，快速算出一个贪心的结果后，可以剪枝。

dp 自下而上自顶向下贪心 + dfs" hl_lines="12

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

class Solution {
    vector<int> cnt;
    int dp(vector<int>& coins, int amount) {
        if(amount < 0) {
            return -1;
        }else if(amount == 0) {
            return 0;
        }
        if(cnt[amount] != 0) {
            return cnt[amount];
        }
        int res = INT_MAX;
        for(auto coin : coins) {
            int subProblem = dp(coins, amount - coin);
            if(subProblem != -1 && subProblem < res) {
                res = subProblem + 1;
            }
        }
        cnt[amount] = res;
        return cnt[amount] == INT_MAX ? -1 : cnt[amount];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) {
            return 0;
        }else if(amount < 0) {
            return -1;
        }
        cnt.resize(amount + 1);
        return dp(coins, amount);
    }
};

class Solution {
private:
    void helper(vector<int>& coins, int amount, int i, int cnt, int& res) {
        if(amount == 0) {
            res = (res <= cnt ? res : cnt);
            return;
        }
        if(i == coins.size()) {
            return;
        }
        // 得到结果之后只接收更优的结果以剪枝
        for(int j = amount / coins[i]; j >= 0 && j + cnt < res; j--) {
            helper(coins, amount - j * coins[i], i + 1, cnt + j, res);
        }
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) {
            return 0;
        }
        sort(coins.rbegin(), coins.rend());
        int res = amount + 1;
        helper(coins, amount, 0, 0, res);
        return res == amount + 1 ? -1 : res;
    }
};

最后更新: July 23, 2022