# Memoizing finite horizon dynamic programming

So I am trying to program a simple finite horizon dynamic programming problem.

I’m trying to use memoization to speed-up computation time.

``````using Optim

V2dict = Dict()

function V2(t, K)
if t >= T
return 0.0
else
if haskey(V2dict, (t, K))
return V2dict[t, K]
else
opt = optimize(K′ -> -(log(K - K′) + β * V2(t+1, K′)), eps(), K, iterations = 100_000)
V2dict[t, K] = Optim.minimum(opt)
return V2dict[t, K]
end
end
end

T = 6
β = 0.95

@time V2(1, 100)
#-6.333197046721626
#  2.846427 seconds (10.56 M allocations: 611.703 MiB, 4.81% gc time)
``````

I have two questions:
Is that how memoization is supposed to be implemented?
Why is `V2dict` saving many keys for each `t`? I am only trying to save the optimal values for `V2`:

``````V2dict
Dict{Any,Any} with 1799 entries:
(4, 3.32187e-5)  => -24.3578
(5, 5.22198e-15) => 32.9762
(5, 4.50844e-16) => 36.4949
(4, 8.69678e-5)  => -25.3202
(5, 2.6052e-12)  => 26.6737
(5, 2.19599e-9)  => 19.9366
(5, 7.22726e-16) => 35.7118
(5, 3.94054e-8)  => 17.0494
(5, 0.118624)    => 2.1318
(4, 1.3312e-14)  => -2.68559
(4, 0.000596086) => -27.245
(3, 4.50844e-16) => 35.5843
(5, 6.72888e-16) => 35.8166
(5, 0.0453104)   => 3.09422
⋮                => ⋮
``````

I have Finite horizon dynamic programming with memorization implemented here

Feel free to take a look for inspiration. The array `memorymat` is my memory.

1 Like