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.

Function Contract

fibonacci(n) expects a non-negative integer n.

It returns the nth Fibonacci number using top-down memoization. The cache key is k, because the value of Fibonacci at k depends only on k.

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.

The DP Checklist

A dynamic programming solution needs four pieces:

• State: what one subproblem means.
• Transition: how a state uses smaller states.
• Base cases: where computation starts.
• Order or cache: how repeated work is avoided.

If any piece is unclear, the implementation will feel like guesswork.

A Small Example

For climbing stairs with one-step or two-step moves:

dp[i] = number of ways to reach step i
dp[i] = dp[i - 1] + dp[i - 2]

The state is one step number. The transition comes from the last move. The base case gives the number of ways to stand at the start.

Why It Works

Dynamic programming works when the larger answer can be built from smaller answers and those smaller answers repeat. Storing each state once turns repeated recursion into controlled reuse.

The correctness depends on the state being complete. If the state omits information that changes future choices, the DP may merge situations that should stay separate.

Complexity Comes From States

After the state is defined, estimate how many different states can exist and how much work each state does.

For Fibonacci with memoization, there are n + 1 states, one for each value from 0 to n. Each state does constant work after its smaller states are available, so the time and space are O(n).

Many DP costs have this shape:

number of states * work per state

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.

Another common mistake is starting with the table size before defining the state. The table shape should come from the state definition.

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.

Do not use DP when a greedy choice is provably enough or when subproblems do not overlap.

The Main Point

Dynamic programming is state plus recurrence plus storage. It helps when the same state appears repeatedly.