解题思路

• 本题是典型的完全背包-组合数问题。每种硬币可无限使用，且“顺序不同视为同一种组合”，因此应当按**先枚举硬币、再枚举金额（升序）**的方式转移，避免将同一组合按排列重复计数。
• 设 dp[s] 表示凑成金额 s 的组合数。初始化 dp[0]=1（凑成 0 元有 1 种“什么都不选”的方式）。
• 转移：对每个硬币面额 c，对 s 从 c 到 amount，执行 dp[s] += dp[s - c]。最终答案为 dp[amount]。
• 当 amount=0 时，答案为 1；若无法凑出，则 dp[amount] 自然为 0。

复杂度分析

Leetcode 518.零钱兑换II-原题链接

题面描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请计算并返回可以凑成总金额的硬币组合数（顺序不同视为同一种组合）。如果任意硬币组合都无法凑出总金额，返回 0。 假设每种面额的硬币都有无限个。题目数据保证结果符合 64 位带符号整数。

输入格式

• 第一行两个整数 N, amount，分别表示硬币种类数和总金额。
• 第二行包含 N 个互不相同的正整数，表示 coins[i] 的面额。

输出格式

输出一个整数，表示能够凑成总金额的组合数。

数据范围

• $1 \le N \le 300$
• $1 \le \text{coins}[i] \le 5000$，且两两不同
• $0 \le \text{amount} \le 5000$

输入样例

3 5
1 2 5

输出样例

4