-
Notifications
You must be signed in to change notification settings - Fork 32
/
problem.go
51 lines (47 loc) · 976 Bytes
/
problem.go
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
package day350
import "math"
// SmallestNumberOfPerfectSquaresSum returns the number
// of perfect squares that sum up to N.
// Runs in O(2^N) time.
func SmallestNumberOfPerfectSquaresSum(n int) int {
if n < 4 {
return n
}
res := n
for i := 1; i <= n; i++ {
tmp := i * i
if tmp > n {
break
} else {
res = min(res, 1+SmallestNumberOfPerfectSquaresSum(n-tmp))
}
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// SmallestNumberOfPerfectSquaresSumFaster returns the number
// of perfect squares that sum up to N.
// Runs in O(N) time and uses O(N) space for dynamic programming.
func SmallestNumberOfPerfectSquaresSumFaster(n int) int {
dp := make([]int, n+1)
for i := 0; i < 4; i++ {
dp[i] = i
}
for i := 4; i <= n; i++ {
dp[i] = i
for x := 1; x <= int(math.Ceil(math.Sqrt(float64(i)))); x++ {
tmp := x * x
if tmp > i {
break
} else {
dp[i] = min(dp[i], 1+dp[i-tmp])
}
}
}
return dp[n]
}