What is dynamic programming and when should you use it?

Dynamic programming solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result to avoid redundant computation. Use it when a problem has two properties: optimal substructure, meaning the optimal solution contains optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems are solved repeatedly. Recognize DP when the problem asks for the maximum, minimum, number of ways, or whether something is possible, and brute-force recursion would recompute the same states many times.