Dynamic Programming

Dynamic Programming (DP) is a technique for solving problems by breaking them down into smaller subproblems, solving each subproblem only once, and storing its solution (often in a table) to avoid redundant computation. It is especially useful for problems with overlapping subproblems (when the same computation is needed multiple times) and optimal substructure (when the solution to a larger problem can be constructed efficiently from solutions to smaller subproblems).

DP generally involves:

1. Defining a table to store results of subproblems.
2. Setting up base cases for the smallest subproblems.
3. Filling the table iteratively or recursively using previously computed values.