【Ruby】【アルゴリズム】メモ化再帰。メモのサイズに気をつける

最強最速アルゴリズマー養成講座
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ

　
この連載、難しいよ。。ごめんね。

問題

A[i]に関して、
i<=0のとき、A[i] = 1
i>0のとき、A[i] = A[i/p-x] + A[i/q-y]
と定義する。n、p、q、x、yが与えられた時、A[n]を求めなさい。
ただし、nは10^13以下、p,qは2以上10^9以下、x、yは0以上10^9以下とします

ポイント

メモ化する。
連想配列で値を記憶することでメモリの無駄を防ぐ（これは知ってた！）
iが一定数以下の場合のみ、A(i)を記憶する
　

コード

@memo1 = {}
@memo2 = {}
@memo3 = {}
def A(i, p, q, x, y)
	return 1 if i <= 0
	return @memo[i] if @memo[i]
	answer = A(i/p - x, p, q, x, y) + A(i/q - y, p, q, x, y)
	@memo[i] = answer 
	@memo[i] = answer if i < 1000000
	@memo[i] = answer if i < 1000
	answer
end
p A(10**13,2,3,4,123456)
p ObjectSpace.memsize_of(@memo1)
p ObjectSpace.memsize_of(@memo2)
p ObjectSpace.memsize_of(@memo3)

　
■実行結果

13475773
"---"
13818244
7525036
25132

　
メモ化！分かりやすい！