1. 5

  2. 2

    Fun quote, but just so people are aware, “dynamic programming” is very different from “dynamically typed languages”.

    The author of the article seems to be aware of this difference and doesn’t really explain it much, but you can tell from a lot of the comments that people are confused. Dynamic programming is the process of decomposing a big problem into smaller subunits, a process formalized/pioneered by Bellman.

    1. 3

      To clarify, dynamic program is a particular way of decomposing a big problem into smaller subunits, which depends on the property that the optimal solution to the smaller subproblems is a subsolution of the optimal solution to the larger problem. This is not true for all problems, but it is true for many interesting problems, e.g. Viterbi decoding and longest-common-subsequence “diff” computation.

      Bellman’s approach was to systematically solve all the smaller subproblems first, working from smallest to largest, which is a little different from memoization, where you work from the top down, which is a little more complicated but often dramatically more efficient (e.g. in Packrat parsers). Some people apply the term “dynamic programming” only to the bottom-up approach, while others include the top-down approach too.

      1. 1

        Argh. Dynamic programming.

      2. 2

        The comments seem apropos given that Harper was using this story from Bellman to support a hypothesis that people prefer “dynamic languages” because the word “dynamic” has positive connotations. Mostly I just thought Bellman’s anecdote was amusing.

      3. 1

        I recommend reading the comments, which are a lot more interesting than the article itself.