给定金额 N 与硬币面值集合 C（每种无限），计算组成 N 的方案数（硬币顺序不影响结果）。

Write a program to figure out how many different ways we can produce a change for N cents, assuming we had an infinite supply of each of the C = C1, C2,...Cm coins. The order in which the coins are placed makes no effect.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

分类: problem-solving

标签: DP, Coin Change

目标公司: IBM

参考答案摘要

Use dynamic programming: dp[i][j] represents ways to make amount i using first j coins. Recurrence dp[i][j] = dp[i][j-1] + dp[i-coin[j]][j] when i-coin[j] >= 0.

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。