题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。

题解

  1. 定义状态：

$dp[i]$表示用所给的面值的硬币凑成金额$i$所需的最少的硬币个数。

  1. 设计状态转移方程：

$$ \forall coin \in coins, 当 i \geqslant coin，且 dp[i - coin] \neq -1 时, dp[i] = std::min(dp[i], dp[i - coin] + 1) $$

  1. 初始化：

对于 amount 为 0 的情况，所需的硬币数也为 0，因此：$dp[0] = 0$

  1. 递推求解：

这里我们使用了一个小技巧，默认将$dp$的值都填充为INT_MAX，这样就可以避免对-1这个负数做特殊的判断和处理，相当于我们用INT_MAX 来代理了-1。

#include <vector>
#include <climits>

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