登录查看题面
登录后即可查看完整题面内容。
会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
- 本题是典型的完全背包-组合数问题。每种硬币可无限使用，且“顺序不同视为同一种组合”，因此应当按**先枚举硬币、再枚举金额（升序）**的方式转移，避免将同一组合按排列重复计数。
- 设
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。
复杂度分析
P4422.LeetCode.518.零钱兑换II
