メモ化再歸 (problem 15 in Project Euler)
Project EulerのProblem 15を解いた。
最初はbigパッケージを使つて組み合はせを計算したが、メモ化再歸使つた方法でも解いてみた。
func PE0015Memoization(n int) int64 {
memo := make([]int64, (n+1)*(n+1))
return routeNumber(n, n, n+1, memo)
}
func routeNumber(i, j, n int, memo []int64) int64 {
if i < 0 || j < 0 {
return 0
} else if i == 0 && j == 0 {
return 1
} else if memo[j*n+i] > 0 {
return memo[j*n+i]
} else if memo[i*n+j] > 0 {
return memo[i*n+j]
}
memo[j*n+i] = routeNumber(i-1, j, n, memo) + routeNumber(i, j-1, n, memo)
return memo[j*n+i]
}
bigパッケージを使用して組み合はせを計算するより速かつた。
% go test -run PE0015 -bench PE0015 -benchmem
Benchmark_PE0015-4 300000 9816 ns/op 3440 B/op 86 allocs/op
Benchmark_PE0015Dp-4 100000 12500 ns/op 4096 B/op 1 allocs/op
Benchmark_PE0015Memoization-4 300000 5701 ns/op 4096 B/op 1 allocs/op
PASS
ok github.com/py0n/project_euler 6.166s