[imslavko]

This is a comment to demonstrate the differences between DP and memoized recursion to people in the sibling comments.

When I was learning DP vs Memoization I thought Floyd-Washall algorithm to find shortest path length between all pairs of nodes in a graph is a good example of DP that wouldn't work the same way with memoization.

In FW algorithm, because of the order of filling up the table and discarding old values on the go, we are able to run the algorithm only using O(n^2) memory, but if we were to run it in a memoized recursive fashion, I would guess you will have to do with O(n^3) memory.

Another example is when a recurrence in DP only depends on the previous row (if we are going row by row) and you can only keep around O(n) memory swapping two rows representing the current row and the previous one. In a recursive black-boxy memoization method you will have to do with a full O(n^2) memory usage.

Finally, there is a technique to do DP on a table using O(n) memory vs O(n^2) and recovering the optimal path by recursively splitting the table into halves and only storing O(1) rows at a time. This technique is more complicated to explain in an HN comment tho.

Update: forgot the simplest example: fibonacci numbers. In the top-down approach, you would memoize results based on the index of the fib number, so you would need an array of results caching O(n) values. But if you build it up bottom-up, you can get away with only using two variables: previous and current and the do something like:

    prev, cur = cur, prev + cur

[agbell]

That is interesting but I still don't totally get how DP is different from simple memoization.

Your fib example can be expressed as corecursion, and in fact, its an example often used to explain it.

  val fibsViaUnfold =
      unfold((res0, res1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) }

    fibsViaUnfold.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8)

That's scala, but should work anywhere where we can produce a lazy stream of values.

Here is a python version from wikipedia

  def nth_factorial(k):
    n, f = 0, 1
    while n < k:
        n, f = n + 1, f * (n + 1)
    yield f

Is DP a techique to arrive at the corecursive solution?

[zodiac]

There's a "simple memoization" version of fibonacci that takes more space than `fibsViaUnfold`. I think the term "simple memoization" (and equivalents used in these comments) are a bit too imprecise to be useful.

[hvidgaard]

DP is a mathematically term describing certain problems. It does not state that you need to save all solutions to sub problems. If you do have a DP problem, the fastest way to solve it is with recursion and memoization as needed because of the properties of the problem.

[imslavko]

I am not arguing with this. In my comment my intend was to show that the distinction between the memoized top-down approach and bottom-up (the approach that is usually taught as DP in a classroom) is significant in some memory optimizations.