Hacker News Reader

I wonder how much mechanical sympathy the Dynamic programming (DP) has as opposed to brute force or other simpler techniques. On paper it seems like a smart technique, in reality, I have rarely seen that being used in critical production systems. In fact, anything recursion-esque is eschewed. Can someone comment on their experience in implementing DP in critical production systems or beyond the scope of programming contest, academia.

View on HN

In general, it has great mechanical sympathy. You need to split your larger problem into smaller sub-problems, and then figure out which sub-problems depend on each other using the recursive formulation. Once you have done that, there should be no more need to have a stack, so you can just use an array to store the results of the depended on problems, and a loop to change which problem is being solved.

This article doesn't make the final step from recursion to loop but you would probably want to if you were doing DP in production.

Edit: Actually the article does make this jump. See the last code snippet before the conclusions section. Note also the second note after the snippet, which explains that the snippet itself uses a larger array than is necessary.

Reply on news.ycombinator.com