[rifung]

> 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"

[chillee]

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