Dynamic Programming (DP)

Dynamic Programming solves problems by breaking them into smaller, overlapping subproblems. It solves each subproblem once, stores the results, and uses these stored results to solve larger problems efficiently. Think of it like building a Lego model: build small pieces first, save them, then assemble the final model.

Example: Climbing stairs with 1 or 2 steps at a time. To find the number of ways to reach the top, combine the ways to get to the previous two steps, storing each result to avoid recalculating.

Divide-and-Conquer

Divide-and-Conquer splits a problem into smaller, independent subproblems, solves each separately, and then combines their solutions. It’s like cutting a pizza into slices, eating each slice, and then combining them in your tummy. This approach gives you an optimal solution for each subproblem, but not necessarily the best global solution in all cases.

Example: Sorting a list with Merge Sort: split the list into two, sort each half, then merge them into a sorted list.

Key Differences

1. Subproblems:
   • DP: Overlapping subproblems, solved once.
   • Divide-and-Conquer: Independent subproblems, solved separately.
2. Storage:
   • DP: Stores subproblem solutions.
   • Divide-and-Conquer: Doesn’t typically store solutions.
3. Approach:
   • DP: Bottom-up.
   • Divide-and-Conquer: Top-down, optimal at each step but not always globally optimal.