Ask HN: Have you ever used Dynamic programming in your dev job?

It really is not.

Memoization has the same time complexity as dynamic programming. But it has much worse space complexity.

First some approximate definitions: The tasks to which memoization and dynamic programming are typically useful are those in which a problem can be decomposed into subproblems, and subsubproblems, and so on, where problem->subproblem dependency is many-to-many, not one-to-many. That is, the dependency graph is a DAG, not a tree. By memoization I mean the process of computing the solution to a function by first looking up in a hash table to see if the solution has already been found, and only computing the solution and storing it if it has not been found. By dynamic programming I mean the bottom-up process of first solving all of the lowest level decomposed subproblems, then solving the next higher level subproblems using the solutions found at the lower level, then the next higher level using the solutions found so far, and so on up to the desired top-level problem.

Whether memoization will do the job depends on the nature of your task. In some tasks the higher-level problems depend on simultaneously knowing the answers to all of the subproblems at every level. For those kinds of problems memoization will be just fine.

But for many dynamic programming tasks, you don't need to keep around all the low-level problems: just the most immediate ones. For example, it's often the case that once you've computed problem layer N, you can get rid of all the layers 0...N-1. They're not necessary to compute problem layer N+1. For these kinds of problems the space cost of dynamic programming is just in keeping that immediate layer N. But memoization has no way of forgetting these layers, because not only is it top-down, but it's also typically depth-first. As a result, by the time you solve the final layer, you have all of the previous layers stored in your hash table.