• 问题来源
• 问题简介

  找零，给你提供无限的零钱和一个需找的钱数，问可以用最少几张零钱完成？若无法完成，则返回-1。
  注：零钱面额是不固定的。

解题思路

• coins: 零钱面额
• amount: 需找的钱数
• dp[i]: amount为i时所需的做少零钱数。1 <= i <= amount

• 则dp[i]的值为（初始化为无穷大）
  • 无穷大 : i < 0
  • 0 : i == 0
  • min(dp[i-coins[1]], dp[i-coins[2]], …., dp[i-coins[n]]) + 1 : 1 <= i <= amount

Code

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

运行结果