LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i] 表示要凑成金额 i 最少需要的硬币数

class Solution {
 public:
  int coinChange(vector<int>& coins, int amount) {
    if (empty(coins)) {
      return -1;
    }
    // 假设全用 1 也不可能用 amout + 1 个，用初始值表示无法组合
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
      for (auto& x : coins) {
        if (i >= x) {
          dp[i] = min(dp[i], dp[i - x] + 1);
        }
      }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
  }
};