1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 |
- /*
- * @Description:
- * @Version: 1.0
- * @Autor: zhuyijun
- * @Date: 2021-11-10 22:49:50
- * @LastEditTime: 2021-11-11 00:01:43
- */
- /*
- 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
- 计算并返回可以凑成总金额所需的 最少的硬币个数
- 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
- 你可以认为每种硬币的数量是无限的。
- 示例 1:
- 输入:coins = [1, 2, 5], amount = 11
- 输出:3
- 解释:11 = 5 + 5 + 1
- */
- #include <bits/stdc++.h>
- using namespace std;
- int helper(vector<int>& coins, int amount, vector<int>& list) {
- if (amount == 0) return 0;
- if (amount < 0) return -1;
- if (list[amount] != -1) return list[amount];
- int res = INT_MAX;
- for (int i = 0; i < coins.size(); i++) {
- int temp = helper(coins, amount - coins[i], list);
- if (temp == -1) continue;
- res = min(res, temp + 1);
- }
- if (res == INT_MAX) {
- res = -1;
- }
- list[amount] = res;
- return list[amount];
- }
- // 暴力递归解法 超时
- int coinChange1(vector<int>& coins, int amount) {
- vector<int> list(amount + 1, -1);
- return helper(coins, amount, list);
- }
- // dp 数组迭代解法
- int coinChange(vector<int>& coins, int amount) {
- vector<int> list(amount + 1, amount + 1);
- list[0] = 0;
- for (int i = 0; i < list.size(); i++) {
- for (int coin : coins) {
- if (i - coin < 0) {
- continue;
- }
- list[i] = min(list[i], 1 + list[i - coin]);
- }
- }
- return (list[amount] == amount + 1) ? -1 : list[amount];
- }
- int main() {
- vector<int> list{186, 419, 83, 408};
- cout << coinChange(list, 6249);
- }
|