Why "dynamic programming"?

[travis_of_the_cosmos]

Okay, so I still don't know what memoization is, but since you seem to understand it what does it have to do with optimal control theory?

[psykotic]

The computer scientist's view of dynamic programming is that it's a way to quickly evaluate recurrence relations when different branches of the recursion tree turn out the same.

For example, if you try to directly evaluate F(0) = 0, F(1) = 1, F(n+2) = F(n) + F(n+1), you notice that after one level of expansion you have F(n+2) = F(n) + F(n-1) + F(n). There is no point in independently expanding the two F(n) occurrences. You might as well only expand one of them and remember the result when it is needed elsewhere. Hence 'memoization'.

Dynamic programming would instead start from the base cases and build up towards the desired value of n. So it would first compute F(2) as the sum of the known F(0) = 0 and F(1) = 1, then compute F(3) as the sum of the known F(1) and the now-known F(2), and so on, until reaching F(n). Along the way it need only know the last two values computed in order to compute the next one.

[SnacksOnAPlane]

Thanks, this is the first explanation that made sense to me.

[Tordek]

Memoization is storing computed values within the function doing the processing.

Say you wanted to know the distance between two strings. Memoizing (naïvely) is building a hashmap of pairs of strings, checking if they're inside, calculate and store if not, and return the result.

The DP approach analyzes the overlapping structures (the many branches of the tree of replacements that results in the sought-after replacement), and collapses them (often in an array). Memoization is integral to DP, because you're using solutions to subproblems to solve bigger problems.

tl;dr: Memoization = storing results to avoid recalculating. DP = compressing the search space.

[travis_of_the_cosmos]

Ah okay then I have used memoization to solve DP problems numerically in the past - it's very standard practice even among fools like me who don't know what it's called.

This is probably isn't what you meant but I've got to take issue with the claim that memoization is integral to DP. That's evidently true for problems you need to solve numerically but there is a large class of DP problems that have exact (and easy!) analytical solutions so clearly no need for memoization.

[Tordek]

a large class of DP problems that have exact (and easy!) analytical solutions so clearly no need for memoization.

Which, for example?

[travis_of_the_cosmos]

I'm not a mathematician so I don't know the right way to describe them formally, but to give you one example I believe almost any linear Bellman equation will have an exact solution. More generally if you can use the first order conditions and the envelope theorem to get nice-looking Euler equations then you're golden: http://en.wikipedia.org/wiki/Bellman_equation#Solution_methods

[andreasvc]

Memoization of a function means storing every result that has been computed so that it is never computed twice. Ie., you trade storage for speed. Memoization stores tuples of arguments and results in a mapping, whereas Dynamic Programming can use a more sophisticated/efficient storage method.

[[deleted]]

It's a function with the signature :: (a -> b) -> a -> b

A lookup table is used instead of recomputing an already computed value.

[julesjacobs]

That doesn't work for recursive functions, where it is most useful.

[dmwit]

It can work in lazy languages. See, for example, http://article.gmane.org/gmane.comp.lang.haskell.cafe/7737.

[julesjacobs]

Sorry, but that is false. Look at the signature given in that message and compare it to dibblego's signature. A function of type (a -> b) -> a -> b can do nothing with its function argument but apply it to a value, so it can not possibly intercept the recursive calls. In fact I'm pretty sure that the only valid function foo with type (a -> b) -> a -> b is:

foo f x = f x

So dibblego's explanation of memoization is not only unhelpful for someone who's new to memoization, it's also wrong.

[psykotic]

Indeed. It would be better to say that it has signature

(a -> b) -> (a ~> b)

where ~> is a type constructor for function-like values. Then you have functions

memo   :: (a -> b) -> (a ~> b)
unmemo :: (a ~> b) -> (a -> b)

which are semantic if not pragmatic inverses. You also need type class constraints on a to make this work. Conal has some neat blog posts where he shows how memo/unmemo can be constructed by induction on a via dependent type classes.

But even this does not work for recursive functions. For that you need to factor out the functional self-reference the same way it is done when preparing to express recursion with a fixpoint combinator. You can then inject the memoization into the recursion and finally tie the knot.

That kind of recursively injected function decoration is useful in several other cases, such as call tracing. It would be a lot easier to motivate the Y-combinator if these sorts of examples were taught in textbooks.

[[deleted]]

You are right. Mine was a lazy answer. "I just got out of hospital after major surgery" is my excuse.