What is Dynamic Programming?

Dynamic Programming (DP) is a problem-solving technique that breaks complex problems into smaller subproblems and stores their solutions to avoid recomputing them. It's like solving a jigsaw puzzle: once you figure out how to fit a piece, you remember it instead of trying again.

The Key Idea:

• Break down: Divide problem into smaller subproblems
• Store solutions: Remember answers to subproblems (memoization)
• Reuse: Use stored solutions instead of recalculating
• Build up: Solve bigger problems using smaller solutions

When to Use DP:

• Overlapping subproblems: Same subproblems appear multiple times
• Optimal substructure: Optimal solution contains optimal solutions to subproblems
• Examples: Fibonacci, shortest path, knapsack problem

Approaches:

• Top-down: Recursive with memoization (start from the problem, work down)
• Bottom-up: Iterative, build from smallest to largest

Classic Example - Fibonacci:

Without DP: Calculate fib(5) recalculates fib(3) multiple times With DP: Calculate once, store it, reuse it