11–20 of 225 posts
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
This is harder than it sounds though.
DP problems tend to be solvable in only a couple lines of code, but the tough part is deciding what to recurve on, and what to memoize.
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down. For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1). With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10). Following on from this, you usually build up the…
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
2. The meat of the problem is understanding how to formulate it such that this "recursion" is possible.
Point two is often non-trivial so your "just" -- while technically correct -- isn't true in practice. If you solve a variety of medium and difficult DP problems, it will be clear why.
Eg: https://www.hackerrank.com/domains/algorithms?filters%5Bsubd...
(I have no affiliation with the site)
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way that memoized recursion makes it computationally easy.
For example, sometimes you might have a problem where the simple DP approach takes n^3 space, but with some trickery you can get it down to n^2.
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
> So "DP" is just recursion with memoization? Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way th…
This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even have a chance at solving them, so really they just test whether the person has learned DP, rather than other algo problems where you can at least try to claim that it's a proxy for "general problem solving ability". And DP comes up almost never in the real world (and when it does come up, you're often still better off taking a heuristic/inexact approach), so testing if the candidate knows DP is also almost completely useless.
If you're an interviewer at a company that asks DP questions, please reconsider. There are almost certainly alternatives that are more fair and higher-signal.
Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?
Exercises from a standard algorithm textbook like Kleinberg and Tardos should give enough practice in solving these problems. Not all of them are straightforward.
Earlier quoted context omitted.
> So "DP" is just recursion with memoization? Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way th…
So, what about something relatively straightforward? Like Fibonacci. Is it "DP" if I recurse+cache?