Home Memo

メモ化再歸 (problem 15 in Project Euler)

舊暦

  • 平成廿玖年神無月拾陸日 (日・甲子・晴)

メモ化再歸 (problem 15 in Project Euler)

Project EulerProblem 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