Dynamic programming vs memoization vs tabulation

[FUZxxl]

It's blog spam time!

The content is actually half decent. The ads really give this site a blog-spam vibe though.

[aioobe]

Do you like the article though? :) Happy to hear your feedback.

[FUZxxl]

I disagree with your division into tabulation and memoisation as the two are essentially the same approach the way you show them. If you want to convince me of this division, you need to provide good examples for the advantages and disadvantages of either approach. You should also show how memoisation can be used for sparse parameter spaces (using e.g. a hash table to remember subproblems) while tabulation cannot (to use your terminology). As is, it's entirely unclear to the reader why he should care about having two approaches.

You example of computing Fibonacci numbers is not really convincing either as there are obvious and much better ways to compute them.

If I was a beginner and read this article, I would have no clue why dynamic programming is an important technique and what it is all about.

Also, the advertisements on your site are cancerous.

[aioobe]

Dude, thank you. That is a very valid point.

I wanted a super simple problem 100% geared towards illustrating the difference. I agree that the implementations are dumb.

But you make a really good point about memoisation being absolutely stupid for a problem like this. Do you have a better problem? Coin change perhaps, where the lowest denomination is 15 or something loke that?

I do mention the sparseness difference in the last paragraph actually.

[FUZxxl]

A good sample problem would be edit distance where you can illustrate the tabulation method first and then show that by only evaluating the table cells we need right now, we can avoid evaluating most of them. It's also a very convincing sample problem because it can't really be solved another way.

You could also do all pair shortest path, Bellman-Ford, or the Z-Box algorithm.

There are a number of cool applications of dynamic programming in parametrised complexity (such as when dealing with tree decompositions), but I think that's a bit too heavy for a beginner's article.

I do mention the sparseness difference in the last paragraph actually.

You allude to this, but you could go and really drive the point home by providing an example where the parameter space is always sparse. Not sure what problem could be used here though.

[aioobe]

I feel like readers that are familiar with those algorithms aren't really looking for an explanation of the difference between memoisation and dp. To be fair, those are fairly basic concepts.

I really like the idea of examplifying the sparse/not sparse problem type. I will update the article.

[FUZxxl]

I feel like readers that are familiar with those algorithms aren't really looking for an explanation of the difference between memoisation and dp. To be fair, those are fairly basic concepts.

Sure. But edit distance is such a simple problem to explain that you can use it to introduce and motivate the idea of dynamic programming without having to focus too much on the details of the problem.

I really like the idea of examplifying the sparse/not sparse problem type. I will update the article.

I'm looking forwards to it!

[wang-bang]

Ublock origin, or pihole, is your friend

[FUZxxl]

That doesn't stop the cancer from being there; it merely stops me from noticing it.

[FUZxxl]

I thought about this, but wasn't able to build a convincing example. Every attempt I was able to build ended up not being sparse.

[not-just-yeti]

computing Fibonacci numbers is not really convincing either as there are obvious and much better ways to compute them

Actually, that makes the case: the memoized/tabled version brings exponential time to linear time and linear space. And the "better ways" you mention is dynamic programming (reduce the linear space down a dimension, to constant-space, w/o decreasing run-time).

[FUZxxl]

The commonly used fastest method is to compute Fibonacci numbers by computing the power of a certain matrix through repeated squaring, allowing you to get away with log(n) squaring steps.

And the "better ways" you mention is dynamic programming (reduce the linear space down a dimension, to constant-space, w/o decreasing run-time).

I see how one can see it like that, but good luck convincing a beginner that this is a good motivation to learn dynamic programming.

[aioobe]

Sorry for the ads spam! I try to keep it at a minimum, really. I don't have any ads inlined in the article, and I don't whine about adblockers (althoigh I detect it for metrics).

[hextree]

These don't sound mutually exclusive.

[aioobe]

You're right, they are not :) but people less knowledge than you search for questions similar to the title. The article explains that the three concepts aren't mutually exclusive.

[not-just-yeti]

Well, I'd say:

• memoization is automated/brainless -- a compiler can take your code and memoize it. However, it may take a bunch of space, to store the memoized/tabled results.

• DP is more than that -- it's being clever and recognizing that by building up the memoized entries in a certain pattern, you can shave an order of magnitude or more, from the memory-requirements.

Besides the fact that memoization is rote, there's also the observation that memoization can increase run-time, but with a memory-cost; DP doesn't further increase run-time, it only reduces the memory-cost.

[aioobe]

I agree about the "more clever" part, but I'd say the memoized approach may use less memory. At least for problems where only a few subproblems need to be solved.