Hacker News Reader

Comment by et2o | Hacker News Reader

Favorite examples for applications of dynamic programming? Mine are sequence alignment/BLAST in bioinformatics, but I'm sure there are many of which I am not aware in other fields.

View on HN

Ditto, my first "Ahah!" moment for DP was actually in a bioinformatics class, implementing Needleman–Wunsch global sequence alignment using a Blosum64 matrix door transition weights. (Details that aren't as impressive as they sound.)

I ended up using it as the basis for another extra-credit project that demonstrated the algorithm with a GUI: Select inputs, choose speed, hit Play, watch the numbers and lines, etc.

Anyway, it's stayed with me as my go-to DP example.

Line breaking. The Knuth-Plass algorithm I implemented is my all-time favorite piece of code.

That’s one of my favorites too, although I remember it being one of the easier implementations from my college course. We just did it with fixed width fonts, of course, but the results were still so impressing.

There are lots of interesting competitive programming problems (and their related algorithms) that involve it. For example, it was important in the solution to a problem in the UKIEPC (UK & Irish programming contest to gear up for the ACM ICPC) this past weekend: https://domjudge.bath.ac.uk/domjudge/public/problem.php?id=3... :)

I guess someone have to mention finding an optimal line wrap for a paragraph of text.

https://doi.org/10.1002%2Fspe.4380111102

Dont need DP here since there is an obviously better iterative approach, BUT, the easiest demonstration of DP value is the naive Recursive algo for Fibonacci sequence generation vs the DP+Recursive algo.

Stereo image matching - specifically semi-global matching. The general idea is still considered a state of the art method.

All of Reinforcement Learning :)

Image stitching is pretty fun!

That sounds like it could have some things in common with the DNA-sequence alignment of the parent comment, both dealing with overlap. Is that so?

Yes, it have a lot of common.

Reinforcement Learning

I think really just "Value Iteration" (which isn't just used in RL). Reinforcement Learning itself is a problem setting and there are solutions in RL that don't use dynamic programming (for example, policy gradient methods).

Well of course :) but it’s a cute method to solve certain MDPs

Reply on news.ycombinator.com