Related:

Real-world dynamic programming: https://news.ycombinator.com/item?id=20285242 (66 comments)

Parallel seam carving: https://news.ycombinator.com/item?id=24117330 (37 comments)

Seam carving (2020) [video] https://news.ycombinator.com/item?id=26844121 (35 comments)

Seam carving (Wikipedia) https://news.ycombinator.com/item?id=21192868 (11 comments)

I bet that if this algorithm had come up today it would be called AI resizing

Kind of a meta question here but I'm so baffled by the apparent stupidity of that comment that I really have to ask myself, what are you trying to do by posting it. At worst you're trolling, at best you're simply displaying your ignorance of DP uses as being a kind of knowledge, that there aren't many applications.

I mean off the top of my head, matrix chain multiplication and database optimisation. But a simple look on a wiki page would have found you more <https://en.wikipedia.org/wiki/Dynamic_programming> and a simple web search would have found you even more. So why post?

Indeed.

I would wager that over the last several decades BLAST (basic local alignment search tool) has done more to advance our knowledge of biology than any other algorithm.

https://en.wikipedia.org/wiki/BLAST_(biotechnology)

BLAST isn't a dynamic programming algorithm. It's not guaranteed to find an optimal solution, unlike a DP algorithm. It has some elements of DP, but that's it.

"BLAST is a heuristic method which means that it is a dynamic programming algorithm..."

https://bioinformaticsreview.com/20210503/how-blast-works-co...

"The heart of many well-known programs is a dynamic programming algorithm, or a fast approximation of one, including sequence database search programs like BLAST..."

https://www.nature.com/articles/nbt0704-909

All DP algorithms guarantee an optimal result. It's a defining characteristic of DP. BLAST doesn't. I'm really surprised that you're attempting to debate this.

That's not true. You can of course use DP for heuristic and approximation algorithms. There's an FPTAS for Knapsack using DP, for instance.

DDG disagrees.

https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic...

I'm clearly not going to understand your motivation so I think I'll stop here.

(edit: There is absolutely nothing stopping heuristics and DP being combined; in fact they have to be in eg. database optimisation. A pure DP solution to query optimisation will be optimal, but will take unbounded (lthough finite) time, which is unacceptable. DP and heuristics are combined to both guide the DP search and bound it after a strict time (usually a couple of seconds CPU) by when it is hopefully 'good enough').

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.

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)

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