Hacker News Reader

Comment by mlevental | Hacker News Reader

gonna take this opportunity to ask for advice: i have an MS in CS and i've gone through all of CLRS twice (yes really all of it and really twice - once for my grad algos class and once in prep for interviews - and i still don't have whatever intuition i need to be able to effortlessly do DP. it's honestly kind of maddening - mincut/maxflow, RSA, knuth-morris-pratt etc are all completely obvious to me and i can whip them out pretty much effortlessly - but DP i struggle to find the optimal substructure and formulate bottom up (yes i can memoize but that's not clever enough for you know who). what's the magic combinatorial perspective/intuition that enables people to construct dp solutions so quickly??? yes i've read vazirani and gone through the clemson examples and etc. and skiena and sedgwick whatever but the problem is they're mostly all rehashings of the same solutions/perspectives. looking forward to this book's perspective.

View on HN

Forget about efficiency for the moment and focus on discovering the underlying recursive problem.

LOTS of people struggle with dynamic programming. But in my experience, 90% of the difficulty with dynamic programming is actually discomfort with recursion, which is why I talk about recursive backtracking first.

Try reading Chapter 2. My goal in that chapter is to show the process of deriving recursive solutions---how to think about the problem, and what questions to ask---rather than just presenting the solution as a fait accompli.

I do have to assume that you believe in the Recursion Fairy, though. That's probably the hardest step. Computer scientists are TERRIBLE at delegating.

> Recursion Fairy

I mentioned this elsewhere but figured I'd bring it up here since you're the author.

I've tried explaining recursion in a lot of ways like this, such as "just assume it will work", "trust yourself", and "turn off your brain". (The first two are paraphrases from Matthew Flatt, the latter is from Will Byrd.)

I think "Recursion Fairy" is my favorite way to phrase the same idea. I think there's something about the nature of invoking a sense of magic in the phrasing that might help people really believe that it's okay to just let the recursion do its thing and not think about it too much. I'll definitely be using "Recursion Fairy" when (if) I end up explaining recursion again.

Thanks for making your material available for free! Cheers!

i don't have a problem with recursion per se - certainly things like tree traversals (e.g. minimax) are very very obvious to me and for example just a couple of days ago i was thinking about AD for recursively defined functions - but optimal substructure (what i think CLRS calls overlapping subproblems) is what i have trouble with. anyway thank you writing the book - i look forward to reading it and getting yet another perspective.

This book has about 26 pages dedicated to Dynamic Programming (the remaining 36 pages in the chapter detail different exercise problems but I'm sure are just as educational).

I think a strong foundation in recognizing the recurrence is key to becoming better at Dynamic Programming. If you're not able to first see the recurrence, then you're doomed to rote-learn a la videos on youtube where the main focus is table filling (I'm looking at you, Tushar Roy). Here's a snippet from the DP chapter in Erickson's book:

> In a nutshell, dynamic programming is recursion without repetition. Dynamic programming algorithms store the solutions of intermediate subproblems, often but not always in some kind of array or table. Many algorithms students (and instructors, and textbooks) make the mistake of focusing on the table— because tables are easy and familiar—instead of the much more important (and difficult) task of finding a correct recurrence. As long as we memoize the correct recurrence, an explicit table isn’t really necessary, but if the recurrence is incorrect, we are well and truly hosed.

On a quick skim of the chapter, here's what it offers that other traditional book chapters don't:

* Progressive optimization of memoized solutions. The example used is Fibonacci where each recurrence is cached, then it's transformed into an iterative for-loop based solution where a table/array is filled, and finally 2 variables are used instead of the whole array to store intermediate solutions.

* Dynamic Programming on trees (both as a datastructure for storing intermediate solutions and sometimes as a problem ex: Optimal BST construction)

I think if you find those algorithms obvious and you're able to write memoized solutions, then you already know most of what you need to know about dynamic programming. For example, Dijkstra's algorithm for shortest paths can be seen as DP.

The main thing is to write down a formulation for the answer for n in terms of answers for smaller n, or the answer for (n, k) in terms of answers for smaller (n, k). (And don't worry about how you'd compute them, just focus on getting a correct expression in terms of smaller ones. http://okasaki.blogspot.com/2008/10/score-one-for-induction....)

It can be tricky to formulate exactly what you're counting / measuring (e.g. what's "k" and what's the quantity you're optimizing for (n, k)), but once you have that, and once you have the recurrence, you can consider it a separate (and independent) step to figure out in which order to compute the values, so that you have each value by the time you need it (i.e. the bottom-up formulation that you said is the tricky part for you).

Beyond that I guess lots of practice with problems… e.g. about a decade ago there used to be weekly(?) TopCoder contests with editorials written later explaining the solutions (and the problems were graded by difficulty and even how many people solved it), and the DPs could get quite tricky. I believe those are still happening, and now there are other resources like LeetCode or whatnot.

Do you have an example of a problem that you struggled with, to see what's missing?

"Dijkstra's algorithm for shortest paths can be seen as DP"

Really? Sure, if the graph is a dag, but then Dijkstra is overkill.

Hmm. I'll have to think about this one.

+1 for the Okasaki shoutout.

Hmm, I wrote that from vague memory, and perhaps that's debatable! (There seem to be different communities that use “dynamic programming” slightly differently.)

But my main point was: if one can look at the shortest-path problem and formulate something like

distance(v) = min_{u->v} (distance(u) + edge_length(u, v))

then one probably has a handle on whatever it is that's hard about dynamic programming. Actually Wikipedia cites some references that consider Dijkstra's algorithm a case of DP: https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algo... and the same text (Wikipedia doesn't care about “self-plagiarism”) is also on the DP page where Dijkstra's algorithm is given as the first example: https://en.wikipedia.org/w/index.php?title=Dynamic_programmi...

Here's an old mathematical perspective that treats dynamic programming as analogous to the calculus of variations. Very different from a how it's usually talked about, I think. I haven't read much of it, but perhaps the change in perspective will be helpful to you:

https://www.rand.org/content/dam/rand/pubs/reports/2006/R441...

Dynamic programming in CS and dynamic programming in operations research share almost nothing besides the name.

i'm familiar with this (through stochastic control and reinforcement learning and general econ stuff) but it's not really useful for the whiteboard coding style DP that FAANG asks.

I'm honestly somewhat surprised that you-know-who is asking DP problems with that degree of complexity. Are you applying for a research/math-heavy role? If you're unlucky enough to see DP, usually it's pretty basic and memoization is considered fine, unless things have changed very recently. If they required that degree of rigor for regular SWE jobs, a lot of people I know certainly wouldn't be there.

> If you're unlucky enough to see DP, usually it's pretty basic and memoization is considered fine, unless things have changed very recently. If they required that degree of rigor for regular SWE jobs, a lot of people I know certainly wouldn't be there.

Did you interview in the past two years at the so-called FAANG companies? 'Leetcoding' has raised the bar considerably, even (or especially, in some cases) for senior positions.

Reply on news.ycombinator.com