Hacker News Reader

Comment by chillee | Hacker News Reader

This is one definition, but I don't think it's the common one. The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler overlapping subproblems that can be solved independently.

Solving it with recursion/memoization vs. bottom-up is merely an implementation detail, while DP refers to a class of algorithms.

EDIT: Corrected definition of DP.

View on HN

> The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler subproblems that can be solved independently

I dont think that's sufficient? I thought DP also implies you actually reuse the answers from subproblems.

From https://en.m.wikipedia.org/wiki/Dynamic_programming

"There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead"

Yeah, you're right. The subproblems must overlap.

I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions.

And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.

Reply on news.ycombinator.com