从组合数量DP恢复硬币面值：逐金额验证新增一币

题意与假设

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

• 给出0..N金额的精确非负整数ways，硬币面值唯一且正，恢复所有≤N面值。
• 币值>N不会影响观察，无法据此恢复；若是有序排列数、有限硬币或重复币种，本文推导不适用。

解题路线

1. 维护已识别小面值的组合dp。到金额v，尚未识别更大面值都不能凑v，所以ways[v]−dp[v]只能为0或1。
2. 差0代表没有币v；差1代表新增一枚面值v，因为用v构成金额v只有[ v ]一种。按coin外层、amount升序更新无限组合。
3. 差其他值或任意更新后超过目标ways均说明合同下不一致；最终整数组相等才接受。拒绝脏输入比只返回猜测硬币更重要。

手动走一遍

币[2,3]在金额0..5的ways=[1,0,1,1,1,1]，到2识别币2，到3识别币3，最终重算匹配。ways=[1,2]不可能：金额1最多由唯一币1组成一种，差2应报错。

Python 参考实现

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

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

def recover_coins(ways):
    if not ways or ways[0] != 1 or any(type(x) is not int or x < 0 for x in ways):
        raise ValueError("nonnegative integer unordered ways, including dp[0]=1 required")
    n = len(ways) - 1
    dp = [1] + [0] * n
    coins = []
    for value in range(1, n + 1):
        delta = ways[value] - dp[value]
        if delta == 0:
            continue
        if delta != 1:
            raise ValueError("inconsistent combination counts")
        coins.append(value)
        for amount in range(value,n+1):
            dp[amount] += dp[amount-value]
        if any(dp[amount] > ways[amount] for amount in range(n+1)):
            raise ValueError("inconsistent combination counts")
    if dp != list(ways):
        raise ValueError("inconsistent combination counts")
    return coins

复杂度

O(N²)最坏时间（币数≤N，每更新及校验扫至N），O(N)空间；组合数巨大时整数算术位成本另计。

易错点与追问

容易失分的边界

• dp[0]=0会让所有更新消失。
• amount逆序会实现每币至多一次，错误恢复无限组合合同。

继续深挖

• 只有dp[1..N]时如何补充dp[0]合同并验证？
• 币种带库存上限，为什么差0/1判定不足？