[面试题 08.11][中等][动态规划][背包] 硬币

题目描述

面试题 08.11. 硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

说明：

注意:

你可以假设：

• 0 <= n (总金额) <= 1000000

解题思路

标准的完全背包问题, 朴素地将状态定义为dp[i][v], 表示前i种面值的硬币构成价值为v的方案数量. 需要进行3层循环: 总面值, 硬币数量, 内部查找可能的关联位置. 本题在时间复杂度和空间复杂度上都有优化的空间, 参考Leetcode题解: 硬币.

class Solution:
    def waysToChange(self, n: int) -> int:
        mod = 1000000007
        coins = [25, 10, 5, 1]

        dp = [0] * (n + 1)  # 滚动数组
        dp[0] = 1  # 当总价值为0时, 不计入任何硬币可以满足, 也是一种匹配的方式, 记为1
        for coin in coins:
            for i in range(coin, n + 1):  # 对于当前coin, 比coin更小总价值的不考虑
                dp[i] = dp[i] + dp[i - coin]
        return dp[-1] % mod