有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n<100000)，有多少中组合可以组成n分钱？

这是一个比较经典的动态规划问题，可以使用动态规划算法来解决。

首先，我们定义一个一维数组 dp，其中 dp[i] 表示组成 i 分钱所需的硬币组合数。因为每种硬币数量无限，所以在计算 dp[i] 时，我们需要考虑使用当前硬币和不使用当前硬币两种情况。

对于第一种情况，即使用当前硬币，那么组成 i 分钱的组合数就等于组成 i-coin 分钱的组合数加上当前硬币的一种组合数，其中 coin 表示当前硬币的面值。

对于第二种情况，即不使用当前硬币，那么组成 i 分钱的组合数就等于组成 i 分钱的组合数。

因此，我们可以得到状态转移方程：

dp[i] = dp[i] + dp[i-coin]

其中，coin 可以取 1 分、2 分、5 分、10 分这四种硬币。

最终，dp[n] 就是组成 n 分钱的组合数。

以下是 Python 代码实现：

def coinChange(n):
    coins = [1, 2, 5, 10]
    dp = [0] * (n+1)
    dp[0] = 1
    for coin in coins:
        for i in range(coin, n+1):
            dp[i] += dp[i-coin]
    return dp[n]

这个算法的时间复杂度是 O(n)，可以在较短的时间内得到结果。

相关问题

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n<100000)，有多少中组合可以组成n分钱

这是一道经典的动态规划问题，可以使用动态规划求解。

设 $dp[i]$ 表示组成 $i$ 分钱的方案数，则有：

$$
dp[i] = dp[i-1] + dp[i-2] + dp[i-5] + dp[i-10]
$$

其中，$dp[i-1]$ 表示在组成 $i$ 分钱的方案中包含了一枚 $1$ 分硬币，$dp[i-2]$ 表示在组成 $i$ 分钱的方案中包含了一枚 $2$ 分硬币，$dp[i-5]$ 表示在组成 $i$ 分钱的方案中包含了一枚 $5$ 分硬币，$dp[i-10]$ 表示在组成 $i$ 分钱的方案中包含了一枚 $10$ 分硬币。

边界条件为 $dp[0]=1$，即不选取任何硬币时，方案数为 $1$。

最终答案为 $dp[n]$。

下面是该问题的 Python 代码实现：

def coin_combinations(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i >= 1:
            dp[i] += dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        if i >= 5:
            dp[i] += dp[i-5]
        if i >= 10:
            dp[i] += dp[i-10]
    return dp[n]

例如，输入 $n=12$，则输出 $dp[12]=61$，表示有 $61$ 种不同的组合方式可以组成 $12$ 分钱。

将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？ 输入格式: 输入在一行中给出待换的零钱数额x∈(8,100)。 输出格式: 要求按5分、2分和1分硬币的数量依次从大到小的顺序，输出各种换法。每行输出一种换法，格式为：“fen5:5分硬币数量, fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count = 换法个数”。

这是一个硬币换零问题。可以使用递归算法来求解。对于给定的零钱数额x，枚举使用5分、2分和1分硬币的数量，当零钱数额x减去使用的硬币数量不小于8时，递归调用算法，并将硬币数量加入结果中，最后输出结果和换法个数。