News for hackers. Stuff that matters.

A comment on Dynamic Progamming: First Principles. Parent comment

Re:Dynamic Progamming: First Principles by zerr on Wednesday October 25, 2017 @09:11AM (#15549761)
I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...
[ Parent | on HN ]
Re:Dynamic Progamming: First Principles by fokinsean on Wednesday October 25, 2017 @09:26AM (#15549870)
You're not alone! Went down the whole nine yards in college, and come exam time knapsack was toast!

However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work.

I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache.

Oh yeah and another important detail is something something solving subproblems :p

[ Parent | on HN ]
Re:Dynamic Progamming: First Principles by zerr on Wednesday October 25, 2017 @09:50AM (#15550076)
Yes, divide-and-conquer where subproblems overlap.
[ Parent | on HN ]