Elements of Dynamic Programming

Optimal substructure and overlapping subproblems — the reasons a recurrence exists and memoization helps.

How this maps to DP

Every DP solution in practice has three explicit parts: a recurrence relation, memoization (or an equivalent tabulation table), and base cases. The two elements below explain why those parts exist.

DP recurrence relation (needs optimal substructure)

Optimal substructure: an optimal solution to the whole problem is built from optimal solutions to subproblems after you fix a first decision (last coin, first rod piece, take/skip an item, etc.).

That structure is exactly what you write as a recurrence: the value for a state equals an aggregate (min, max, sum) of values at other states plus local data.

Example

optimal whole → expressed using optimal smaller instances

Without optimal substructure, a simple one-state recurrence may not exist — you might need more information in the state or a different model.

DP memoization (needs overlapping subproblems)

Overlapping subproblems: the naive recursive tree for the same recurrence asks for the same state many times (e.g. F(3) many times in naive Fibonacci).

Memoization stores dp(state) the first time it is computed and reuses it. The recurrence is unchanged; only work sharing changes.

Example

many paths in the recursion tree → same (state) argument → one stored answer

If subproblems were always disjoint (as in typical divide-and-conquer where each subproblem is unique at its size), caching would not reduce asymptotic time.

DP base case

Recurrences must stop. Base cases are the instances where the answer is known by definition: dp(0) = 0, F(0) and F(1), dp(0, c) = 0, no items, zero amount, and so on.

Bases are not separate from “DP theory” — they are part of the same definition as the recurrence. Wrong bases break both memoized and tabulated code.

DP vs. greedy (short)

Greedy adds a greedy choice property: one local choice is always safe, so you do not need to explore alternatives. DP keeps the recurrence that considers several branches (max/min/sum) because no single local rule is always optimal (0/1 knapsack, arbitrary coin sets).

Summary

Optimal substructure → you can write a recurrence. Overlapping subproblems → memoization (or tabulation) is worth it. Base cases → recursion terminates and the table is well-defined.

Pseudocode

Conceptual checklist tying elements to implementation:

1HAS-DP-STRUCTURE(problem)
2  optimal_substructure?  → can write recurrence dp(state) from smaller states
3  overlapping_subproblems? → memo / table avoids recomputation
4  clear_base_cases? → smallest states have fixed values
5  if all yes → recursive DP with memo or bottom-up table

Complexity

Once states and transitions are fixed, complexity follows from counting states — not from these definitions alone.

Complexity Analysis

Time Complexity

Problem-specific after state space is fixed

Space Complexity

Typically O(number of states) for memo

Greedy may be O(n log n) when DP is not needed

Growth Rate Comparison

DP recurrence relation (needs optimal substructure)

That structure is exactly what you write as a recurrence: the value for a state equals an aggregate (min, max, sum) of values at other states plus local data.

Example

optimal whole → expressed using optimal smaller instances

Without optimal substructure, a simple one-state recurrence may not exist — you might need more information in the state or a different model.

DP memoization (needs overlapping subproblems)

Overlapping subproblems: the naive recursive tree for the same recurrence asks for the same state many times (e.g. F(3) many times in naive Fibonacci).

Memoization stores dp(state) the first time it is computed and reuses it. The recurrence is unchanged; only work sharing changes.

Example

many paths in the recursion tree → same (state) argument → one stored answer

If subproblems were always disjoint (as in typical divide-and-conquer where each subproblem is unique at its size), caching would not reduce asymptotic time.

DP base case

Recurrences must stop. Base cases are the instances where the answer is known by definition: dp(0) = 0, F(0) and F(1), dp(0, c) = 0, no items, zero amount, and so on.

Bases are not separate from “DP theory” — they are part of the same definition as the recurrence. Wrong bases break both memoized and tabulated code.

Pseudocode

Conceptual checklist tying elements to implementation:

1HAS-DP-STRUCTURE(problem)
2  optimal_substructure?  → can write recurrence dp(state) from smaller states
3  overlapping_subproblems? → memo / table avoids recomputation
4  clear_base_cases? → smallest states have fixed values
5  if all yes → recursive DP with memo or bottom-up table

Complexity

Once states and transitions are fixed, complexity follows from counting states — not from these definitions alone.

Complexity Analysis

Time Complexity

Problem-specific after state space is fixed

Space Complexity

Typically O(number of states) for memo

Greedy may be O(n log n) when DP is not needed