アルゴリズム・パズル(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秒。自分の回答例ではメモ化できない。