Seam Carving (2018)

There aren't many useful applications. People who think otherwise are on par with delusional interviewers that feel compelled to ask problems with DP solutions. The vast majority of us will go our entire careers without needing to solve the Towers of Hanoi or the Egg Drop Puzzle.

Knapsack/subset sum, travelling salesman, longest common subsequence, dynamic time warp/edit distance/sequence alignment, Q-learning, line breaking/paragraph layout, ...

I cut almost a minute off of our startup time by removing a recursive nightmare one of my coworkers inflicted on some code I wrote by replacing the whole thing with DP.

But you’d have to look pretty close to see that’s what I did because unlike him I’m not obsessed with people thinking I’m clever. I’d rather be seen as wise.

(I started fixing it because we had found a couple mystery bugs caused by his solution not being reentrant. By the time I had full code branch coverage, it was actually six separate bugs I fixed)