TikTok Coin Change：最少枚数与组合数的两个状态

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 相关描述同时出现标准题编号与“组合数非排列数”，两者目标冲突，不能确定实际所求。
• 训练正整数币值、无限使用、amount非负，重复币值视同一种；代码同时返回最少枚数与组合数。

解题路线

1. 最少数dp[s]=min(dp[s-c]+1)，dp[0]=0，无解标记；目标是优化而不是计数，金额递增确保依赖较小值已完成。
2. 组合数ways[0]=1，币种在外金额正向在内，逐种加入该币种使用0..多次的可能，保留一个规范币种顺序避免同组合多次排列。
3. 金额在外对所有币种累加计数会统计有序序列；例如1+2与2+1成两个结果。0/负币值破坏有限状态与单调依赖，提前拒绝。
4. amount=0最少0且有一种空组合；无币且amount>0最少-1、组合0。输入重复面额不应把两张同币值当不同类型，除非正式合同另有说明。
5. 这两种训练不能替代补齐实际题目目标，审阅清单保留目标冲突，不宣称当时必考其中一种。

手动走一遍

coins=[1,2]、amount3：最少2枚，组合{1+1+1,1+2}共2；有序序列则3。coins=[2]、amount3无解(-1,0)。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def coin_change(coins, amount):
    """Positive integer denominations, unlimited use, nonnegative integer amount.
    Return (minimum count or -1, unordered combination count)."""
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError('positive coins and nonnegative amount required')
    coins = sorted(set(coins))
    minimum = [amount+1] * (amount+1)
    minimum[0] = 0
    for value in range(1, amount+1):
        minimum[value] = min([minimum[value-c]+1 for c in coins if c <= value] or [amount+1])
    ways = [0] * (amount+1)
    ways[0] = 1
    for coin in coins:
        for value in range(coin, amount+1):
            ways[value] += ways[value-coin]
    return (-1 if minimum[amount] > amount else minimum[amount], ways[amount])

复杂度

D不同币值、金额A，O(DA)时间和O(A)空间，伪多项式；组合计数的大整数位数另计。

易错点与追问

容易失分的边界

• 把最少枚数与组合数混成一个答案。
• 组合数金额外循环变排列。
• 币值0形成无界组合。

继续深挖

• 如果每币只能一次如何改方向？
• 如何重建最少解？