アルゴリズム・パズル（Ruby）
問題
ひとつのテーブルに配置できる最大の人数が10人のとき、1人だけのテーブルができないように100人を配置したい。そのパターン数を求めよ。
なお、分け方のパターンだけ求め、誰がどこに座るかは考えないものとする。例えば6人の場合、[2, 2, 2], [2, 4], [3, 3], [6] の4通りになる。
解いてみた
co = 0 try = ->(left, max) { if left.zero? co += 1 else max.downto(2) do |num| next if left < num try.(left - num, num) end end } try.(100, 10) puts co #=>437420
答えは正しいが、1.3秒ほどかかる。
模範解答
メモ化している。
memo = {}
try = ->(left, min) {
return memo[[left, min]] if memo[[left, min]]
return 0 if left < 0
return 1 if left.zero?
co = 0
(min..10).each do |num|
co += try.(left - num, num)
end
memo[[left, min]] = co
}
puts try.(100, 2) #=>437420
メモ化する前は3.1秒、メモ化後は0.01秒。自分の回答例ではメモ化できない。
