2 ms·

Plenty already exist which support dynamic programming "natively." For example, the 'memoize' function in clojure.

• alangpierce 8y ago
  I bet there are ways a programming language could support dynamic programming better than just having a memoize function in the standard library. Examples: * For a given DP algorithm, you might evaluate it top-down (recursive memoized call) or bottom-up (filling in the table values in topological order). Top-down is easiest to implement, but bottom-up can avoid stack depth limits and I think can be more efficient if implemented well. A language specifically crafted for it might let you write the simpler recursive implementation and efficiently evaluate it bottom-up. * Sometimes you might want to run the same DP algorithm in different contexts, e.g. operating on different data sets (where the data set is constant for a recursion tree). Keeping the data set (or even a pointer to it) in each cache entry is wasteful if your cache has 100 million things in it, and passing it down as a parameter is also not as efficient as it could be. I guess closures may solve the problem, but maybe there are smarter ways that a language could help here.