Is there a reason that “When space complexity must be minimized.” isn’t a good answer for when dynamic programming is NOT be the appropriate algorithmic approach?
Here is question 10 in the quiz:
In which scenario would dynamic programming NOT be the appropriate algorithmic approach?
When space complexity must be minimized.
When subproblems are independent and don’t overlap.
When the problem can be broken into smaller subproblems.
When the problem requires finding an optimal solution.
You should consider using dynamic programming in the following scenarios:
The problem can be broken down into overlapping subproblems.
The problem exhibits optimal substructure.
A naive recursive solution would involve repeated calculations.
You need to optimize for time complexity at the cost of space complexity.
To me, it seems like “When space complexity must be minimized.” is correct because dp uses more space to optimize time. “You need to optimize for time complexity at the cost of space complexity.”
“When subproblems are independent and don’t overlap.” also seems correct because from the review “The problem can be broken down into overlapping subproblems.”
Is it a situation where one answer is MORE correct out of two correct answers?
* Overlapping Subproblems: The same smaller problems appear multiple times when solving the larger problem. Instead of recalculating these subproblems repeatedly, we store their solutions.
When the same smaller problems repeat, then dynamic programming is appropriate.
If they are independent and don’t overlap, then DP isn’t the right approach.
