文章目录

• 1. 题目
• • 1.1 示例
  • 1.2 说明
  • 1.3 提示
  • 1.4 进阶
• 2. 解法一
• • 2.1 分析
  • 2.2 解答
  • 2.3 复杂度

1. 题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 0 0 。

假设每一种面额的硬币有无限个。题目数据保证结果符合 32 32 32 位带符号整数。

1.1 示例

• 示例 1 1 1：

• 输入： amount = 5 ， coins = [1, 2, 5]
• 输出： 4 4 4
• 解释： 有四种方式可以凑成总金额：
  5 = 5 5=5 5=5
  5 = 2 + 2 + 1 5=2+2+1 5=2+2+1
  5 = 2 + 1 + 1 + 1 5=2+1+1+1 5=2+1+1+1
  5 = 1 + 1 + 1 + 1 + 1 5=1+1+1+1+1 5=1+1+1+1+1

• 示例 2 2 2：

• 输入： amount = 3 ， coins = [2]
• 输出： 0 0 0
• 解释： 只用面额 2 2 2 的硬币不能凑成总金额 3 3 3 。

• 示例 3 3 3：

• 输入： amount = 10 ， coins = [10]
• 输出： 1 1 1

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/coin-change-2

1.3 提示

• 1 ≤ c o i n s . l e n g t h ≤ 300 1 \le coins.length \le 300 1≤coins.length≤300 ；
• 1 ≤ c o i n s [ i ] ≤ 5000 1 \le coins[i] \le 5000 1≤coins[i]≤5000 ；
• coins 中的所有值互不相同 ；
• 0 ≤ a m o u n t ≤ 5000 0 \le amount \le 5000 0≤amount≤5000 。

1.4 进阶

2. 解法一

2.1 分析

这道题中，给定总金额 amount 和数组 coins，要求计算金额之和等于 amount 的硬币组合数。其中，coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。可以通过动态规划的方法计算可能的组合数。用 dp[i] 表示金额之和等于 i 的硬币组合数，目标是求 dp[amount] 。

动态规划的边界是 dp[0] = 1。只有当不选取任何硬币时，金额之和才为 0 0 0，因此只有 1 1 1 种硬币组合。

对于面额为 coin 的硬币，当 coin ≤ i ≤ amount \textit{coin} \le i \le \textit{amount} coin≤i≤amount 时，如果存在一种硬币组合的金额之和等于 i − coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到金额之和等于 i 的一种硬币组合，这意味着金额 i 和 i - coin 的组合数是相等的。因此需要遍历 coins，对于其中的每一种面额的硬币，更新数组 dp 中每个索引大于或等于该面额的元素（即更新 dp[i] ，其中 coin ≤ i ≤ amount \textit{coin} \le i \le \textit{amount} coin≤i≤amount）的值。

由此可以得到动态规划的解题流程：

• 初始化 dp[0] = 1；
• 遍历 coins，对于其中的每个元素 coin，进行如下操作：
  • 遍历 i 从 coin 到 amount，将 dp[i − coin] 的值加到 dp[i] 。
• 最终得到 dp[amount] 的值即为答案。

• 作者： LeetCode-Solution

2.2 解答

from typing import List, Union


class CoinChangePermutations:
    @classmethod
    def permutation(cls, coins: List[int], amount: int) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, len(dp)):
                if i - coin >= 0:
                    dp[i] += dp[i - coin]
        return dp[amount]


def main():
    coins = [1, 2, 5]
    amount = 5
    print(BottomUpIterativeSolution.coin_change(coins, amount))
    print(CoinChangePermutations.permutation(coins, amount))  # 4


if __name__ == '__main__':
    main()

• 执行用时： 128 ms , 在所有 Python3 提交中击败了 82.02% 的用户；
• 内存消耗： 15 MB , 在所有 Python3 提交中击败了 71.55% 的用户。

上述做法不会重复计算不同的排列。因为外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。

2.3 复杂度

• 时间复杂度： O ( amount × n ) O(\textit{amount} \times n) O(amount×n)，其中 amount 是总金额，n 是数组 coins 的长度。需要使用数组 coins 中的每个元素遍历并更新数组 dp 中的每个元素的值。
• 空间复杂度： O ( amount ) O(\textit{amount}) O(amount)，其中 amount 是总金额。需要创建长度为 amount + 1 的数组 dp。