leetcode_cpp/dp/322.cpp

/*
 * @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);
}