カタラン数を計算してみる、その２
前回はfactorialとcombinationでカタラン数を導出しようと、fact 20くらいであっけなくオーバーフローしたけど、チーター本のP.216ではカタラン数をDPで計算してる。けど、問題の解説見ててがあったほうが分かり易いなと何となく思った*1。
を定義した場合
しなかった場合(書籍の解説より引用)
C0=1
で、の一般項は、本の通りになると腑に落ちた。それだけ*2ｗ−
ってわけのいかないので、それでコード書いてみた。けど、本のサンプルのDPは*3よく分からないので
Ruby*4の再帰で書き下すｗ−。
$memo = Array.new(10, 0) $memo[0] = 1 def catalan n return $memo[n] unless $memo[n].zero? $memo[n] = (1..n).to_a.reduce(0){|s,i| #p [s,i] p [$memo] s + catalan(n-i) * catalan(i-1) } $memo[n] end
それっぽい答え出てるけど、早いのかどうかわからないｗ−
P.S.
前回のfactorial使ったのと、今回のrubyコードの時間計測しても大して変わらないな$ time ruby catalan.rb [1, 1] [2, 2] [3, 5] [4, 14] [5, 42] [6, 132] [7, 429] [8, 1430] [9, 4862] [10, 16796] [11, 58786] [12, 208012] [13, 742900] [14, 2674440] [15, 9694845] real 0m0.334s user 0m0.310s sys 0m0.020s$ time ruby catalan_memo.rb [1, 1] [2, 2] [3, 5] [4, 14] [5, 42] [6, 132] [7, 429] [8, 1430] [9, 4862] [10, 16796] [11, 58786] [12, 208012] [13, 742900] [14, 2674440] [15, 9694845] real 0m0.321s user 0m0.300s sys 0m0.010s
最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイドposted with amazlet at 17.03.21
