Solve a problem by combining overlapping sub-problem solutions. Either memoise a top-down recursion, or fill a table bottom-up.

Data Flow (Fibonacci)

Fib(5) tree (naive)                Memoised / tabulated:

         F(5)                       F(0..5):  0  1  1  2  3  5
        /   \                       table size = N
     F(4)   F(3)                    one pass: 1 add
     ...   ...                      O(N) time, O(N) space
                                 or O(1) if you only keep last two

When to use

• Decision tree with overlapping subproblems.
• Optimisation: min / max / count of ways.

Code (Climbing Stairs, bottom-up)

def climb(n):
    a, b = 1, 1           # F(0), F(1)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Pitfalls

• Forgetting to identify the state (parameters of the recursion).
• Wrong cache key — state that depends on too much (cache never hits) or too little (wrong answers).
• Not optimising space — many DP problems only need the last row/column.

Analogy

Calculating chess ratings with an Elo table: each new game updates only the current and previous game — you don’t re-run the whole tournament.

Interview tip: Write the brute force recursion first. If you see duplicate sub-calls, that’s DP. Memoise.