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