3 ms·

Introduction to Dynamic Programming

28 points by prakash 18y ago

newt0311 18y ago
Even more interesting, there are now some compiler optimization algorithms which can theoretically do some of this stuff automatically. Look up incrementalization on citeseerx etc...
- neilc 18y ago
  Very cool. Thanks for mentioning that.
jfarmer 18y ago
I wrote this article over a year ago -- glad to see it's still making the rounds.
- snprbob86 18y ago
  I apologize for being nitpicky, but you shouldn't abuse the tuple assignment syntax. I had to expand out msum2 to be able to read it reasonably.
  - ralph 18y ago
    Agreed. The pseudo-code had it in a more readable style. If it must be compressed onto one line then a = 0; b = (0, 0); c = float('infinity') is preferable if a, b, and c are logically unrelated compared to a, b, c = 0, (0, 0), float('infinity') especially as the list gets longer. Why should the reader first count to find where variable `foo' is on the left-hand side before then counting the same number of places on the right?
  - brent 18y ago
    Are you referring to this line where he initializes 4 variables? bounds, s, t, j = (0,0), -float('infinity'), 0, 0
    - snprbob86 18y ago
      Yes, and the `bounds, s = (j, i+1), t` especially when forced onto the same line as the if statement. See the Python Style Guide: http://www.python.org/dev/peps/pep-0008/ http://www.python.org/dev/peps/pep-0008/ "Compound statements (multiple statements on the same line) are generally discouraged."
      - brent 18y ago
        I agree about compound statements, but I think most people will use the tuple assignment style, especially when its simply initializing variables. There is no reason to expand it beyond one line.
        snprbob86 18y ago
        There is a reason: it reduces the reading distance from variable to initial value. It also reduces the amount of effort you need to exert to map them to each other. This is especially true when you are using () which impact the meaning of ','. There's also no reason to keep it on one line :-) Newlines and equal signs are cheap; go wild!
apu 18y ago
Perhaps I don't understand it fully, but my view of dynamic programming is that you can always get the same benefits using a caching function and just writing your program naturally. This approach has worked for me for a variety of DP problems I've tried, and I've always wondered if there are functions for which the simple memoization trick does not work (although I cannot figure out why that would be the case). Also, this caching code is much easier to read and requires no back-and-forth step in terms of building up some auxiliary array and then backtracing or whatever to get the final results. Can someone provide me a counter-example and some intuition for why caching doesn't work in that case? (Incidentally, in most functional languages, you can write a generic memoization function once and never have to write it again. In Python, you can even write it as a decorator function and then making a function cacheable is as simple as prepending @memoize to it's declaration).
- Psyonic 18y ago
  dynamic programming is usually more efficient. They'll be on the same order, but the constant factor is usually lower. However, if all that matters is that you're not getting into exponential territory, memoization should be fine.
- lacker 18y ago
  I always considered memoization a type of dynamic programming, rather than something different from dynamic programming. Wikipedia at least uses this same nomenclature - http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.org/wiki/Dynamic_programming Anyways, there are cases when memoization takes orders of magnitude more memory. Consider a problem where calculating F(x, y) is dependent on F(x - 1, y) and F(x, y - 1). (Recursively calculating n choose k is one such example.) Let's say F(x, 0) and F(y, 0) are non-recursive, they just take O(1) time. If you use memoization, in order to find F(n, n) you will take O(n^2) memory. But if you fill an array, you can calculate all the F(1, x), then all the F(2, x), and once you have done all the F(2, x) you don't need the memory for the F(1, x) any more. Et cetera. So you only need O(n) memory.

28 points by prakash 18y ago

Even more interesting, there are now some compiler optimization algorithms which can theoretically do some of this stuff automatically. Look up incrementalization on citeseerx etc...

neilc 18y ago
Very cool. Thanks for mentioning that.

jfarmer 18y ago

I wrote this article over a year ago -- glad to see it's still making the rounds.

snprbob86 18y ago
I apologize for being nitpicky, but you shouldn't abuse the tuple assignment syntax. I had to expand out msum2 to be able to read it reasonably.
- ralph 18y ago
  Agreed. The pseudo-code had it in a more readable style. If it must be compressed onto one line then a = 0; b = (0, 0); c = float('infinity') is preferable if a, b, and c are logically unrelated compared to a, b, c = 0, (0, 0), float('infinity') especially as the list gets longer. Why should the reader first count to find where variable `foo' is on the left-hand side before then counting the same number of places on the right?
- brent 18y ago
  Are you referring to this line where he initializes 4 variables? bounds, s, t, j = (0,0), -float('infinity'), 0, 0
  - snprbob86 18y ago
    Yes, and the `bounds, s = (j, i+1), t` especially when forced onto the same line as the if statement. See the Python Style Guide: http://www.python.org/dev/peps/pep-0008/ http://www.python.org/dev/peps/pep-0008/ "Compound statements (multiple statements on the same line) are generally discouraged."
    - brent 18y ago
      I agree about compound statements, but I think most people will use the tuple assignment style, especially when its simply initializing variables. There is no reason to expand it beyond one line.
      - snprbob86 18y ago
        There is a reason: it reduces the reading distance from variable to initial value. It also reduces the amount of effort you need to exert to map them to each other. This is especially true when you are using () which impact the meaning of ','. There's also no reason to keep it on one line :-) Newlines and equal signs are cheap; go wild!

apu 18y ago

Perhaps I don't understand it fully, but my view of dynamic programming is that you can always get the same benefits using a caching function and just writing your program naturally. This approach has worked for me for a variety of DP problems I've tried, and I've always wondered if there are functions for which the simple memoization trick does not work (although I cannot figure out why that would be the case). Also, this caching code is much easier to read and requires no back-and-forth step in terms of building up some auxiliary array and then backtracing or whatever to get the final results. Can someone provide me a counter-example and some intuition for why caching doesn't work in that case? (Incidentally, in most functional languages, you can write a generic memoization function once and never have to write it again. In Python, you can even write it as a decorator function and then making a function cacheable is as simple as prepending @memoize to it's declaration).

Psyonic 18y ago
dynamic programming is usually more efficient. They'll be on the same order, but the constant factor is usually lower. However, if all that matters is that you're not getting into exponential territory, memoization should be fine.
lacker 18y ago
I always considered memoization a type of dynamic programming, rather than something different from dynamic programming. Wikipedia at least uses this same nomenclature - http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.org/wiki/Dynamic_programming Anyways, there are cases when memoization takes orders of magnitude more memory. Consider a problem where calculating F(x, y) is dependent on F(x - 1, y) and F(x, y - 1). (Recursively calculating n choose k is one such example.) Let's say F(x, 0) and F(y, 0) are non-recursive, they just take O(1) time. If you use memoization, in order to find F(n, n) you will take O(n^2) memory. But if you fill an array, you can calculate all the F(1, x), then all the F(2, x), and once you have done all the F(2, x) you don't need the memory for the F(1, x) any more. Et cetera. So you only need O(n) memory.