-
Notifications
You must be signed in to change notification settings - Fork 0
/
322_coin_change.js
70 lines (63 loc) · 1.72 KB
/
322_coin_change.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// tags: #dp #knapsack
// https://leetcode.cn/problems/coin-change/
// version 1
// k is the number of coins, n is the amount
// time: O(k^n) | TLE
// space: O(n)
var coinChange = function (coins, amount) {
if (amount === 0) return 0;
if (amount < 0) return -1;
let min = Infinity;
for (let coin of coins) {
let sub = coinChange(coins, amount - coin);
if (sub === -1) continue;
min = Math.min(min, sub + 1);
}
return min === Infinity ? -1 : min;
};
// version 2
// top-down dp
// time: O(kn) | 120ms
// space: O(n)
var coinChange = function (coins, amount, memo = {}) {
if (amount === 0) return 0;
if (amount < 0) return -1;
if (memo[amount]) return memo[amount];
let min = Infinity;
for (let coin of coins) {
let sub = coinChange(coins, amount - coin, memo);
if (sub === -1) continue;
min = Math.min(min, sub + 1);
}
return (memo[amount] = min === Infinity ? -1 : min);
};
// version 3
// bottom-up dp
// time: O(kn) | 110ms
// space: O(n)
var coinChange = function (coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= amount; i++) {
for (let coin of coins) {
if (i - coin < 0) continue;
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};
// version 4
// bottom-up dp performance tweak
// time: 80ms | beat 100%
var coinChange = function (coins, amount) {
if (!amount) return 0;
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};
console.assert(coinChange([1, 2, 5, 9], 51) === 7);