What is the key idea behind Dynamic Programming?

• A. Divide and conquer without reuse.
• B. Greedy selection
• C. Solve subproblems independently.
• D. Solve subproblems once and reuse their results to build larger solutions.

Answer: (D)

Dynamic programming hinges on solving subproblems once and reusing their results to build larger solutions. When a problem can be broken into overlapping subproblems, you compute a subproblem’s answer and store it. If the same subproblem comes up again, you fetch the stored result instead of recomputing it. This caching turns many exponential-time tasks into efficient polynomial-time solutions, whether you build up a table iteratively (bottom-up) or solve recursively with memoization (top-down). This approach contrasts with solving subproblems independently or making locally optimal greedy choices without reuse.