0322. Coin Change
=================
题目信息
--------
:题号: 0322
:难度: Medium
:主题: 硬币面额、无限使用、最少数量、不可达状态
:原题: `LeetCode 0322 `_
:重点: 每种面额可使用任意次、目标必须恰好组成、无解返回 -1、金额 0 返回 0
题目重述
--------
给定整数数组 ``coins``,其中每个元素是一种正整数硬币面额,以及非负整数 ``amount``。每种面额的硬币数量无限,选择若干硬币使面额总和恰好等于 ``amount``,返回所需硬币的最少数量。
若无法恰好组成目标金额,返回 ``-1``;当 ``amount == 0`` 时不需要任何硬币,返回 ``0``。``coins`` 的长度位于 ``[1, 12]``,每个面额位于 ``[1, 2^31-1]``,``amount`` 位于 ``[0, 10^4]``。
自建示例
--------
同一面额可以重复使用:
.. code-block:: text
输入:coins = [2, 5],amount = 7
输出:2
解释:使用一个 2 和一个 5 可以恰好组成 7,无法只用一枚硬币完成。
目标金额不可达:
.. code-block:: text
输入:coins = [4, 6],amount = 5
输出:-1
解释:任意数量的 4 和 6 之和都不能等于 5。
金额为零:
.. code-block:: text
输入:coins = [9],amount = 0
输出:0
解释:空选择的总金额就是 0,因此不需要硬币。
按金额建立最少硬币数
----------------------
定义 ``dp[x]`` 为恰好组成金额 ``x`` 所需的最少硬币数;不可达状态先设为一个大于任何可能答案的值。``dp[0] = 0`` 是空选择的真实基础。对于当前金额 ``x``,若使用一枚面额 ``coin`` 作为最后一枚硬币,前面的部分必须恰好组成 ``x - coin``,因此可以从 ``dp[x - coin] + 1`` 转移。
金额按从小到大计算,所有转移来源都已经确定。由于同一面额可以无限使用,当前循环再次读取更小金额的状态就自然允许重复使用;而“最后一枚硬币”的枚举覆盖了每一种组合。金额大于 ``amount`` 的面额不可能参与任何解,可以直接跳过。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int coinChange(std::vector& coins, int amount) {
const int impossible = amount + 1;
std::vector dp(amount + 1, impossible);
dp[0] = 0;
for (int current = 1; current <= amount; ++current) {
for (long long coin : coins) {
if (coin > current) continue;
int previous = current - static_cast(coin);
dp[current] = std::min(dp[current], dp[previous] + 1);
}
}
return dp[amount] == impossible ? -1 : dp[amount];
}
};
代码分析
--------
``amount + 1`` 足以作为不可达标记,因为任何可达金额最多使用 ``amount`` 枚面额至少为 1 的硬币;即使从不可达状态加一,也不会产生整数溢出。``coin`` 用 ``long long`` 接收,比较时不会因题目允许的超大面额而发生窄化问题。时间复杂度为 ``O(amount * coins.size())``,额外空间为 ``O(amount)``;金额为零时只读取 ``dp[0]`` 并返回零。