Dynamic Programming Fundamentals

Understand the core principles of dynamic programming: overlapping subproblems, optimal substructure, and how DP differs from divide-and-conquer and greedy approaches.

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler overlapping subproblems, solving each subproblem only once, and storing the result for future use. The name is somewhat misleading — it has nothing to do with "programming" in the coding sense. Richard Bellman coined the term in the 1950s partly because "dynamic" sounded impressive to funding agencies.

At its core, DP is about avoiding redundant computation. If you find yourself solving the same subproblem repeatedly, DP says: "solve it once, store the answer, look it up next time."

The Two Key Properties

For a problem to be solvable by DP, it must have BOTH of these properties:

1. Overlapping Subproblems

The problem can be broken into subproblems that are reused multiple times. This is what distinguishes DP from ordinary divide-and-conquer.

Consider Fibonacci: fib(5) = fib(4) + fib(3), but fib(4) = fib(3) + fib(2). Notice fib(3) is needed twice! In the full recursion tree, the same subproblems appear exponentially many times.

Example

fib(5) / \ fib(4) fib(3) ← fib(3) computed twice! / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

2. Optimal Substructure

An optimal solution to the problem contains optimal solutions to its subproblems. In other words, you can build the best answer from the best answers to smaller pieces.

Example: The shortest path from A to C through B = (shortest path A to B) + (shortest path B to C). You cannot get a shorter A-to-C path by using a suboptimal A-to-B segment.

DP vs Divide-and-Conquer

Both break problems into subproblems, but:

	Divide-and-Conquer	Dynamic Programming
Subproblems	Independent, no overlap	Overlapping, reused
Storage	Not needed (each solved once)	Cache results
Examples	Merge Sort, Quick Sort	Fibonacci, Knapsack
Approach	Recursive	Top-down or bottom-up

Merge sort divides an array into halves — the left half and right half are independent. DP problems have subproblems that share sub-subproblems.

DP vs Greedy

Both find optimal solutions, but:

	Greedy	Dynamic Programming
Choice	Make locally best choice NOW	Consider ALL choices
Correctness	Needs greedy-choice proof	Always correct if properties hold
Efficiency	Usually faster	Usually slower but more general
Examples	Activity selection, Huffman	Knapsack, Edit distance

Greedy makes an irrevocable decision at each step. DP explores all options and picks the best combination. If a problem has the greedy-choice property (locally optimal = globally optimal), use greedy. Otherwise, you need DP.

How to Identify DP Problems

Look for these signals:

"Find the minimum/maximum/optimal..."
"Count the number of ways to..."
"Is it possible to..." (with choices at each step)
Problem has clear choices at each step (include/exclude, go left/right, etc.)
Brute force would try all combinations exponentially

Common DP categories:

Sequence DP: LIS, LCS, edit distance
Knapsack DP: Subset sum, coin change, 0/1 knapsack
Interval DP: Matrix chain, palindrome partitioning
Grid DP: Unique paths, minimum path sum
Tree DP: Max path sum, house robber on tree
State machine DP: Stock buying/selling, regex matching

The DP Recipe

Define state: What information do you need to describe a subproblem?

Example: dp[i] = answer for the first i elements
Example: dp[i][j] = answer using items 1..i with capacity j

Define transition: How do smaller states combine to form larger ones?

Example: dp[i] = max(dp[i-1], dp[i-2] + value[i])

Define base cases: What are the trivial subproblems?

Example: dp[0] = 0, dp[1] = value[1]

Define answer: Which state gives the final answer?

Example: dp[n] or max(dp[i] for all i)

Determine order: Compute states in an order that ensures dependencies are resolved first.

Simple Example: Climbing Stairs

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways to reach step n?

State: dp[i] = number of ways to reach step i Transition: dp[i] = dp[i-1] + dp[i-2] (arrive from step i-1 or i-2) Base: dp[0] = 1, dp[1] = 1 Answer: dp[n]

Example

def climb_stairs(n): if n <= 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

This is literally Fibonacci! dp[5] = 8 ways to climb 5 stairs.

Two Implementation Approaches

Top-Down (Memoization)

Start with the big problem, recursively break it down, cache results.

python example

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

Bottom-Up (Tabulation)

Start with base cases, iteratively build up to the answer.

Example

def fib(n): dp = [0, 1] for i in range(2, n+1): dp.append(dp[-1] + dp[-2]) return dp[n]

Both give the same answers. The next two lessons cover these approaches in detail.

Time Complexity of DP

DP time complexity = (number of states) × (time per state transition)

Fibonacci: n states × O(1) per state = O(n)
Knapsack: n×W states × O(1) per state = O(nW)
LCS: m×n states × O(1) per state = O(mn)
Matrix Chain: n² states × O(n) per state = O(n³)

What is Dynamic Programming?

At its core, DP is about avoiding redundant computation. If you find yourself solving the same subproblem repeatedly, DP says: "solve it once, store the answer, look it up next time."

The Two Key Properties

For a problem to be solvable by DP, it must have BOTH of these properties:

1. Overlapping Subproblems

The problem can be broken into subproblems that are reused multiple times. This is what distinguishes DP from ordinary divide-and-conquer.

Consider Fibonacci: fib(5) = fib(4) + fib(3), but fib(4) = fib(3) + fib(2). Notice fib(3) is needed twice! In the full recursion tree, the same subproblems appear exponentially many times.

Example

fib(5) / \ fib(4) fib(3) ← fib(3) computed twice! / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

2. Optimal Substructure

An optimal solution to the problem contains optimal solutions to its subproblems. In other words, you can build the best answer from the best answers to smaller pieces.

Example: The shortest path from A to C through B = (shortest path A to B) + (shortest path B to C). You cannot get a shorter A-to-C path by using a suboptimal A-to-B segment.

DP vs Divide-and-Conquer

Both break problems into subproblems, but:

	Divide-and-Conquer	Dynamic Programming
Subproblems	Independent, no overlap	Overlapping, reused
Storage	Not needed (each solved once)	Cache results
Examples	Merge Sort, Quick Sort	Fibonacci, Knapsack
Approach	Recursive	Top-down or bottom-up

Merge sort divides an array into halves — the left half and right half are independent. DP problems have subproblems that share sub-subproblems.

DP vs Greedy

Both find optimal solutions, but:

	Greedy	Dynamic Programming
Choice	Make locally best choice NOW	Consider ALL choices
Correctness	Needs greedy-choice proof	Always correct if properties hold
Efficiency	Usually faster	Usually slower but more general
Examples	Activity selection, Huffman	Knapsack, Edit distance

How to Identify DP Problems

Look for these signals:

"Find the minimum/maximum/optimal..."
"Count the number of ways to..."
"Is it possible to..." (with choices at each step)
Problem has clear choices at each step (include/exclude, go left/right, etc.)
Brute force would try all combinations exponentially

Common DP categories:

Sequence DP: LIS, LCS, edit distance
Knapsack DP: Subset sum, coin change, 0/1 knapsack
Interval DP: Matrix chain, palindrome partitioning
Grid DP: Unique paths, minimum path sum
Tree DP: Max path sum, house robber on tree
State machine DP: Stock buying/selling, regex matching

The DP Recipe

Define state: What information do you need to describe a subproblem?

Example: dp[i] = answer for the first i elements
Example: dp[i][j] = answer using items 1..i with capacity j

Define transition: How do smaller states combine to form larger ones?

Example: dp[i] = max(dp[i-1], dp[i-2] + value[i])

Define base cases: What are the trivial subproblems?

Example: dp[0] = 0, dp[1] = value[1]

Define answer: Which state gives the final answer?

Example: dp[n] or max(dp[i] for all i)

Determine order: Compute states in an order that ensures dependencies are resolved first.

Simple Example: Climbing Stairs

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways to reach step n?

State: dp[i] = number of ways to reach step i Transition: dp[i] = dp[i-1] + dp[i-2] (arrive from step i-1 or i-2) Base: dp[0] = 1, dp[1] = 1 Answer: dp[n]

Example

def climb_stairs(n): if n <= 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

This is literally Fibonacci! dp[5] = 8 ways to climb 5 stairs.

Two Implementation Approaches

Top-Down (Memoization)

Start with the big problem, recursively break it down, cache results.

python example

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

Bottom-Up (Tabulation)

Start with base cases, iteratively build up to the answer.

Example

def fib(n): dp = [0, 1] for i in range(2, n+1): dp.append(dp[-1] + dp[-2]) return dp[n]

Both give the same answers. The next two lessons cover these approaches in detail.

Time Complexity of DP

DP time complexity = (number of states) × (time per state transition)

Fibonacci: n states × O(1) per state = O(n)
Knapsack: n×W states × O(1) per state = O(nW)
LCS: m×n states × O(1) per state = O(mn)
Matrix Chain: n² states × O(n) per state = O(n³)

Dynamic Programming Fundamentals

What is Dynamic Programming?

The Two Key Properties

1. Overlapping Subproblems

2. Optimal Substructure

DP vs Divide-and-Conquer

DP vs Greedy

How to Identify DP Problems

The DP Recipe

Simple Example: Climbing Stairs

Two Implementation Approaches

Top-Down (Memoization)

Bottom-Up (Tabulation)

Time Complexity of DP

Continue learning this concept

Dynamic Programming Fundamentals

What is Dynamic Programming?

The Two Key Properties

1. Overlapping Subproblems

2. Optimal Substructure

DP vs Divide-and-Conquer

DP vs Greedy

How to Identify DP Problems

The DP Recipe

Simple Example: Climbing Stairs

Two Implementation Approaches

Top-Down (Memoization)

Bottom-Up (Tabulation)

Time Complexity of DP

Continue learning this concept