forked from TheAlgorithms/TypeScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcoin_change.ts
More file actions
43 lines (37 loc) · 1.15 KB
/
coin_change.ts
File metadata and controls
43 lines (37 loc) · 1.15 KB
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
export interface CoinChange {
minCoins: number
coins: number[]
}
/**
* Given a set of categories of coins C and an amount of money S, the goal is:
* to give change for S but to use a minimum number of coins. Suppose each category of coin has an infinite number of pieces.
* @param money - amon of money.
* @param coins - The coins that are available.
* @returns CoinChange, the minimum number of coins, and which coins are selected
*/
export const coinChange = (money: number, coins: number[]): CoinChange => {
const minCoins: number[] = Array(money + 1).fill(Infinity)
const lastCoin: number[] = Array(money + 1).fill(-1)
minCoins[0] = 0
// Fill in the DP table
for (let i = 0; i < coins.length; i++) {
for (let j = 0; j <= money; j++) {
if (j >= coins[i]) {
if (minCoins[j] > 1 + minCoins[j - coins[i]]) {
minCoins[j] = 1 + minCoins[j - coins[i]]
lastCoin[j] = coins[i]
}
}
}
}
const res: CoinChange = {
minCoins: minCoins[money],
coins: []
}
let total: number = money
while (total > 0) {
res.coins.push(lastCoin[total])
total -= lastCoin[total]
}
return res
}