並んだタイルの塗り方は何通りかというパズルを解く

qiita.com
　

問題

9個の白マスが横一列に並んでいます。このうち、いくつかの白マスを黒く塗ります。ただし、少なくとも一つは黒く塗り、また、黒マスが連続することはありません。
このとき、塗り方は全部で何通りあるでしょう。

Ruby で解いてみた

index: 左から何マス目か
pred: 左隣りの色（左端の場合は nil）

再帰を使っています。

def paint(index, pred = nil)
  return 1 if index == 9
  s = 0
  if index.zero? || pred == :white
    s += paint(index + 1, :white)
    s += paint(index + 1, :black)
  else
    s += paint(index + 1, :white)
  end
  s
end

puts paint(0) - 1    #=>88

答えは88通りです。最後に 1 を引いているのは、これだとすべて白マスで黒く塗らない場合が一つ含まれてしまうからです。
　

メモ化

100マスだとフリーズするので、メモ化してみます。

def paint(index, pred = nil)
  return 1 if index == 100
  return @memo[[index, pred]] if @memo.has_key?([index, pred])
  s = 0
  if index.zero? || pred == :white
    s += paint(index + 1, :white)
    s += paint(index + 1, :black)
  else
    s += paint(index + 1, :white)
  end
  @memo[[index, pred]] = s
end

@memo = {}
puts paint(0) - 1    #=>927372692193078999175