What is dynamic programming and how does it differ from naive recursion?

• A. Dynamic programming stores subproblem results to avoid recomputation, reducing exponential time to polynomial; naive recursion recomputes subproblems
• B. Dynamic programming always uses iterative loops; naive recursion uses memoization
• C. Dynamic programming is unrelated to recursion; naive recursion is faster
• D. Dynamic programming only applies to numerical optimization; naive recursion applies to tree traversals

Answer: (A)

Dynamic programming stores the results of subproblems so each one is solved only once and reused later. This reuse avoids the huge amount of repeated work that happens when subproblems are solved independently each time, which is what makes naive recursive solutions blow up from exponential time to much more manageable, often polynomial time. For example, computing Fibonacci numbers with a naive recursive approach recalculates the same smaller Fibonacci values many times, while a dynamic programming version saves those values in a table and looks them up when needed, cutting the total number of computations dramatically. You can implement dynamic programming either top-down with memoization or bottom-up by filling a table iteratively. The essential idea is clear: store and reuse subproblem results rather than recomputing them.