What is dynamic programming and when should it be used?

Dynamic programming solves complex problems by breaking them into overlapping subproblems, storing solutions to avoid redundant computation (memoization or tabulation). Use DP when: problem has optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems solved multiple times). Common examples: Fibonacci, shortest paths, knapsack. DP trades space for time, reducing exponential complexity to polynomial.