Project Eueler: problem15

問題

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

回答

def root(x,y,c)
  cnt = 0
  return c[x][y] if c[x][y]
  return cnt += 1  if x == MAX_X and y == MAX_Y
  cnt += root(x+1, y, c)  if x < MAX_X
  cnt += root(x, y+1, c)  if y < MAX_Y
  return c[x][y] = cnt
end

b = Time.now
MAX_X ,MAX_Y = 20, 20
cache = Array.new(MAX_X+1)
cache.each_index{|y| cache[y] = Array.new(MAX_Y+1,nil)}
p "cnt #{root(0,0,cache)}"
p "time #{Time.now - b}"

備考

メモ化再帰を使う。メモ化しないと遅すぎて終わらなかった。