Top of Rubyist決定戦の回答: 再帰メモ化

gistfile1.rb

N=10000
M=3

# 再帰・全探索
# i = 残りの数値
# j = 組み合わせ数
# 4 1 = 1
# 4 2 = 4 1 + (2 2 = 2 1 + (0 2 = 1) = 2) = 3
# 4 3 = ...
# O(2**n)?
def rec_solve(i, j)
  return 1 if i == 0 || j == 1
  r = rec_solve(i, j-1) # 4の2, 4の1...
  r += rec_solve(i-j, j) if i >= j # 2の2, ...
  return r;
end

# 再帰メモ化
@memo = Array.new(N+1){ Array.new(M+1){ nil } }
def rec_memo_solve(i, j)
  return 1 if i == 0 || j == 1
  return @memo[i][j] if not @memo[i][j].nil?
  r = rec_solve(i, j-1)
  r += rec_solve(i-j, j) if i >= j
  @memo[i][j] = r
  return r;
end

p rec_memo_solve(N, M)-1