# Memoizing finite horizon dynamic programming

**URL:** <https://discourse.julialang.org/t/memoizing-finite-horizon-dynamic-programming/19731>\
**Category:** Specific Domains\
**Tags:** question\
**Created:** [January 17, 2019, 4:43am UTC](https://discourse.julialang.org/t/memoizing-finite-horizon-dynamic-programming/19731 "2019-01-17T04:43:03Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![amrods](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/amrods/32/2543_2.png) [@amrods](https://discourse.julialang.org/u/amrods)\
**Post date:** [January 17, 2019, 4:43am UTC](https://discourse.julialang.org/t/memoizing-finite-horizon-dynamic-programming/19731/1 "2019-01-17T04:43:03Z")

</div>

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
  ⋮ => ⋮

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [January 17, 2019, 5:49am UTC](https://discourse.julialang.org/t/memoizing-finite-horizon-dynamic-programming/19731/2 "2019-01-17T05:49:08Z")

</div>

I have Finite horizon dynamic programming with memorization implemented here

> <https://github.com/baggepinnen/LTVModels.jl/blob/master/src/seg_bellman.jl#L94>

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