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
71
72
73
74
75
76
| object CoinsCombine {
var i = 0
var j = 0
var k = 0
def main(args: Array[String]): Unit = {
val start = System.currentTimeMillis()
println(coinChange(Array(1, 3, 5), 40))
println(System.currentTimeMillis() - start)
val start1 = System.currentTimeMillis()
println(coinChangeDp(Array(1, 3, 5), 40))
println(System.currentTimeMillis() - start1)
val start2 = System.currentTimeMillis()
println(coinChangeDpIter(Array(1, 3, 5), 40))
println(System.currentTimeMillis() - start2)
println(s"$i $j $k")
}
def coinChange(coins: Array[Int], amount: Int): Int = {
i += 1
if (amount == 0) return 0
var minRes = amount
for (i <- 0 until coins.length) {
val subAmount = amount - coins(i)
if (subAmount < 0) return -1
val sub = coinChange(coins, amount - coins(i))
if (sub != -1) {
minRes = Math.min(minRes, sub + 1)
}
}
if (minRes == amount) -1 else minRes
}
def coinChangeDp(coins: Array[Int], amount: Int): Int = {
val dp = new Array[Int](amount + 1)
dp(0) = 0
coins.foreach(a => dp(a) = 1)
doCoinChangeDp(coins, amount, dp)
}
def doCoinChangeDp(coins: Array[Int], amount: Int, dp: Array[Int]): Int = {
j += 1
if (amount == 0) return 0
var minRes = amount
for (i <- 0 until coins.length) {
val subAmount = amount - coins(i)
if (subAmount < 0) return -1
if (dp(subAmount) != 0) return Math.min(minRes, dp(subAmount) + 1)
val sub = doCoinChangeDp(coins, subAmount, dp)
if (sub != -1) {
minRes = Math.min(minRes, sub + 1)
}
}
if (minRes == amount) -1 else minRes
}
def coinChangeDpIter(coins: Array[Int], amount: Int): Int = {
val dp = new Array[Int](amount + 1)
for (i <- 0 until amount + 1) {
dp(i) = amount + 1
}
dp(0) = 0
coins.foreach(a => dp(a) = 1)
for (i <- 1 until amount + 1) {
for (a <- coins) {
if (i - a >= 0) {
k += 1
dp(i) = Math.min(dp(i - a) + 1, dp(i))
}
}
}
dp(amount)
}
}
|