有 � k 种硬币，面值为 � = { � 1 , ⋯ , � � } X={x 1 ​ ,⋯,x k ​ }的，硬币数量不限。求金额 � N 的币数最小兑换方案。 若存在多个币数最小方案，则给出字典序最小的方案。 例如： � = { 1 , 5 , 10 , 25 , 50 } , 11 分 = 11 × 1 分 = 2 × 5 分 + 1 × 1 分 = 1 × 5 分 + 6 × 1 分 = 1 × 10 分 + 1 × 1 分 X={1,5,10,25,50},11分=11×1分=2×5分+1×1分=1×5分+6×1分=1×10分+1×1分 其中币数最小且字典序最小的是：1分 10分

这是一个经典的硬币找零问题，可以使用动态规划求解。定义状态 dp[i] 表示凑出金额 i 所需的最少硬币数，转移方程为：

dp[i] = min(dp[i - x] + 1)，其中 x 属于硬币面值集合 X，且 i - x >= 0

初始状态为 dp[0] = 0，表示凑出金额为 0 不需要任何硬币。最终的答案即为 dp[N]。

要求字典序最小的方案，可以在转移时记录凑出 dp[i] 所需的最后一枚硬币面值 j，即 dp[i] = dp[i - j] + 1，然后在输出方案时从 dp[N] 逆推回去，每次选择最后一枚硬币面值最小的方案。

下面是参考代码，时间复杂度为 O(Nk)，其中 k 是硬币面值集合的大小。

def coinChange(X, N):
    dp = [float('inf')] * (N + 1)  # 初始化为正无穷
    dp[0] = 0  # 凑出 0 元需要 0 枚硬币
    last_coin = [-1] * (N + 1)  # 记录最后一枚硬币的面值

    for i in range(1, N + 1):
        for x in X:
            if i - x >= 0 and dp[i - x] + 1 < dp[i]:
                dp[i] = dp[i - x] + 1
                last_coin[i] = x

    if dp[N] == float('inf'):  # 无法凑出 N 元
        return -1

    coins = []
    i = N
    while i > 0:
        coins.append(last_coin[i])
        i -= last_coin[i]

    return coins

使用样例：

X = [1, 5, 10, 25, 50]
N = 11
print(coinChange(X, N))  # 输出 [1, 10]

说明：凑出 11 分的最少硬币数为 2，有 3 种方案：1+10、5+6、11×1，其中第一种方案字典序最小，因此选择该方案。