Python代码：简化网友国度货币系统，求解最小货币种数

以下是解决该问题的Python代码： ```python # 读取数据组数 T = int(input()) for _ in range(T): # 读取货币种数 n = int(input()) # 读取面额数组 coins = list(map(int, input().split())) # 对面额数组进行排序 coins.sort() max_amount = coins[-1] # 初始化动态规划数组 dp = [False] * (max_amount + 1) dp[0] = True # 用于记录最终保留的货币数量 ans = 0 for coin in coins: # 如果当前面额不能由之前的面额组合得到，则保留该面额 if not dp[coin]: ans += 1 # 更新动态规划数组 for j in range(coin, max_amount + 1): dp[j] = dp[j] or dp[j - coin] print(ans) ``` 代码解释： 1. 读取输入：首先读取数据的组数`T`，然后对于每组数据，读取货币种数`n`和面额数组`coins`。 2. 排序面额数组：对面额数组进行排序，方便后续处理。 3. 初始化动态规划数组：创建一个长度为`max_amount + 1`的布尔型数组`dp`，其中`dp[i]`表示金额`i`是否可以被表示出来。初始时，`dp[0]`为`True`，因为金额0可以不使用任何货币表示。 4. 遍历面额数组：对于每个面额`coin`，如果`dp[coin]`为`False`，说明该面额不能由之前的面额组合得到，因此保留该面额，并更新动态规划数组。 5. 更新动态规划数组：对于每个可以使用当前面额`coin`表示的金额`j`，更新`dp[j]`为`dp[j] or dp[j - coin]`。 6. 输出结果：最后输出保留的货币数量`ans`。 复杂度分析： - 时间复杂度：$O(T * n * max_amount)$，其中$T$是数据组数，$n$是货币种数，$max_amount$是最大面额。 - 空间复杂度：$O(max_amount)$，主要用于存储动态规划数组。 ######[AI问答 | 529点数解答 | 2025-12-13 10:29:25]