#3715. 最少硬币问题

最少硬币问题

题目描述

给定一些面值为1, 5, 10, 25的硬币,求给定金额m最少需要多少个硬币。你可以无限使用每种硬币。 例如,金额为30时,最少需要3个硬币:25+5。

输入格式

输入一个整数m(1≤m≤10000)。

输出格式

输出一个整数,表示最少需要的硬币数量。

样例

11
2 
30
2 

说明/提示

数据范围:1≤m≤10000。保证O(n^2)以内算法可以在1秒内跑完。

解析

解题思路

最少硬币问题是一个典型的动态规划问题。我们需要找到一种方法来组合给定的硬币面值(1, 5, 10, 25),以使得达到特定金额m的最少硬币数量。通过构建一个动态规划数组,我们可以从较小的问题逐步解决到整个问题。

算法选择理由

使用动态规划是因为它能够有效地将一个大的问题分解成较小的子问题,并且避免重复计算相同的子问题。在这里,我们定义了一个数组dp,其中dp[i]表示达到金额i所需的最少硬币数量。通过迭代每种可能的硬币,我们更新dp数组,直到找到解决整个问题的答案。

复杂度分析

  • 时间复杂度:O(m*n),其中m是金额,n是硬币种类数(这里为4)。对于每个金额,我们需要检查每种硬币的可能性,这确保了算法的效率。
  • 空间复杂度:O(m),因为我们使用了一个大小为m+1的dp数组来存储中间结果。

这种方法确保了在最大规模数据(m=10000)下,算法仍然能在限定的时间内完成,即1秒以内。

来源

AI 生成 · qwen2.5:14b · 普及 · 贪心