Rubyで最短ルート数を探す 〜Rubyでオイラープロジェクトを解こう！Problem15

Problem 15 - Project Eulerより

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

How many routes are there through a 20×20 grid?
2×2グリッドの左上の角からスタートした場合、右下の角に至るには6つのルートがある(引き返しはなし)。
では20×20のグリッドではいくつのルートがあるか。

任意の交点に至るルートは
その真上と左隣の交点からだけなので
そこまでのルートの合計が
任意の交点に至るルートの数になる

交点横一列の要素数の配列を作り
ここに対応する交点に至るルート数を格納する

 def routes(x,y)
   points = Array.new(x+1, 1)
   y.times do |n|
     (points.length).times do |i|
       next if i == 0
       points[i] = points[i-1] + points[i]
     end
   end
   points.last
 end

 routes(20,20) # => 137846528820

これは再帰でもいけそうだ
こちらのほうがエレガントだ

 def routes(x, y)
   return 1 if x == 0 or y == 0
   routes(x, y-1) + routes(y, x-1)
 end

 routes(20, 20) # =>

でもいつまで待っても答えが出ない…