22 ms·
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
by chillee 8y ago
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.
- rifung 8y ago> 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 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"
- chillee 8y agoYeah, you're right. The subproblems must overlap.
- candeira 8y agoI 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.