面试题 08.11. 硬币
文章目录

题目

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

题解

完全背包问题模板 + 求余数

1
2
3
4
5
6
7
8
9
10
11
12
13
var waysToChange = function (n) {
if (n === 0) return 1
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
[1, 5, 10, 25].forEach(coin => {
dp.forEach((e, i) => {
if (i >= coin) {
dp[i] = (dp[i] + dp[i - coin]) % 1000000007
}
})
})
return dp[n]
};

完全背包问题模板

有一点需要注意的是, 这个不考虑排列顺序的情况

对于 元可以排列成 1+1+1 和 1+2 和 2+1, 但是 1+2 和 2+1 会被算作是同一种情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
*
* @param n 金额总数
* @param coinSet 可选硬币数组
* @returns 对于金额总数 n 有多少种组合方法
*/
var change = (n, coinSet) => {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;

coinSet.forEach(c => {
for (i = c; i <= n; i++) {
dp[i] = dp[i - c] + dp[i]
}
})
return dp[n]
}