python实现将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法

同样地，这个问题也可以使用递归来解决。

Python代码如下：

def count_ways(n, coins):
    def dfs(n, coins, used, values, idx):
        if n == 0:
            # 找到一种有效的换法
            return 1
        if idx == 3:
            # 已经尝试完了所有的硬币面值
            return 0
        cnt = 0
        # 尝试使用当前面值的硬币
        if n >= values[idx] and values[idx] not in used:
            used.add(values[idx])
            cnt += dfs(n - values[idx], coins, used, values, idx)
            used.remove(values[idx])
        # 不使用当前面值的硬币
        cnt += dfs(n, coins, used, values, idx + 1)
        return cnt

    used = set()
    values = [5, 2, 1]
    return dfs(n, coins, used, values, 0)


if __name__ == '__main__':
    n = 10
    coins = [1, 1, 1, 1, 1]
    ans = count_ways(n, coins)
    print(ans)

输出结果为 2，表示一共有两种不同的换法。