main.cpp

// Source: https://leetcode.com/problems/coin-change
// Title: Coin Change
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.
//
// Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.
//
// You may assume that you have an infinite number of each kind of coin.
//
// **Example 1:**
//
// ```
// Input: coins = [1,2,5], amount = 11
// Output: 3
// Explanation: 11 = 5 + 5 + 1
// ```
//
// **Example 2:**
//
// ```
// Input: coins = [2], amount = 3
// Output: -1
// ```
//
// **Example 3:**
//
// ```
// Input: coins = [1], amount = 0
// Output: 0
// ```
//
// **Constraints:**
//
// - `1 <= coins.length <= 12`
// - `1 <= coins[i] <= 2^31 - 1`
// - `0 <= amount <= 10^4`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

// DP
//
// Let DP[i] be the number of coins to sum to i.
// DP[i] = INF if it is impossible.
// DP[0] = 0
// For each kind of coin, try to apply this coin to all DP values.
class Solution {
  constexpr static int kInf = INT_MAX / 2;

 public:
  int coinChange(const vector<int>& coins, const int amount) {
    // DP
    auto dp = vector<int>(amount + 1, kInf);
    dp[0] = 0;
    for (const int coin : coins) {
      for (int i = 0; i <= amount - coin; ++i) {
        dp[i + coin] = min(dp[i + coin], dp[i] + 1);
      }
    }

    return dp[amount] >= kInf ? -1 : dp[amount];
  }
};