Dynamic Programming as an Idea

Dynamic programming is the idea of solving a problem by reusing answers to smaller overlapping subproblems.

At the idea level, the important question is: “Am I solving the same smaller problem many times?”

Core Idea

Dynamic programming needs a state, a recurrence, and a way to store results. The state describes one subproblem. The recurrence describes how that state depends on smaller states. Storage prevents repeated work.

This can be written top-down with memoization or bottom-up with tabulation.

Python Example

def fibonacci(n):
    memo = {0: 0, 1: 1}
 
    def solve(k):
        if k not in memo:
            memo[k] = solve(k - 1) + solve(k - 2)
        return memo[k]
 
    return solve(n)

The same Fibonacci values would be recomputed many times without memo.

Common Confusions

Dynamic programming is not just “use an array.” The array or dictionary is only useful after the state and recurrence are clear.

Dynamic programming is also not the same as brute force with caching in every problem. If subproblems do not repeat, caching may not help much.

When To Use It

Use dynamic programming when the problem has repeated subproblems, each subproblem can be identified by a state, and larger answers can be built from smaller answers.