Dynamic Programming Foundations

📋 At a Glance

Aspect	Details
Time to Read	35 minutes
Prerequisites	Part 2 (Recursion), Part 3 (Divide & Conquer)
Key Concepts	Optimal Substructure, Overlapping Subproblems, Memoization, Tabulation
Difficulty	⭐⭐⭐ (Intermediate)

┌─────────────────────────────────────────────────────────────────┐
│              DYNAMIC PROGRAMMING OVERVIEW                       │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  TWO KEY PROPERTIES                                             │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │                                                         │    │
│  │  1. OPTIMAL SUBSTRUCTURE                                │    │
│  │     Optimal solution contains optimal sub-solutions     │    │
│  │                                                         │    │
│  │     fib(5) = fib(4) + fib(3)                            │    │
│  │              ↓         ↓                                │    │
│  │           optimal   optimal                             │    │
│  │                                                         │    │
│  │  2. OVERLAPPING SUBPROBLEMS                             │    │
│  │     Same subproblems solved multiple times              │    │
│  │                                                         │    │
│  │           fib(5)                                        │    │
│  │          /      \                                       │    │
│  │      fib(4)    fib(3)  ← computed twice!                │    │
│  │      /    \    /    \                                   │    │
│  │   fib(3) fib(2) fib(2) fib(1)                           │    │
│  │                                                         │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
│  TWO APPROACHES                                                 │
│  ┌──────────────────────┐  ┌──────────────────────┐             │
│  │ TOP-DOWN             │  │ BOTTOM-UP            │             │
│  │ (Memoization)        │  │ (Tabulation)         │             │
│  │                      │  │                      │             │
│  │ Start from problem   │  │ Start from base      │             │
│  │ Recurse down         │  │ Build up to answer   │             │
│  │ Cache results        │  │ Fill table           │             │
│  │                      │  │                      │             │
│  │ Natural, lazy        │  │ Iterative, complete  │             │
│  └──────────────────────┘  └──────────────────────┘             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

Recognize DP problems: Identify optimal substructure and overlapping subproblems
Choose the right approach: Decide between memoization and tabulation
Define states correctly: The hardest and most important skill
Write transitions: Convert recurrence relations to code
Optimize space: Reduce memory when only recent states matter

🔥 Production Story: The Shipping Cost Disaster

A logistics company needed to calculate optimal shipping routes. Their system was timing out during peak hours.

The Problem

JAVA(25 lines)
Code
Loading syntax highlighter...

The Investigation

The team traced the call tree:

minCost(0, 50)
├── minCost(1, 50)
│   ├── minCost(2, 50)
│   │   ├── minCost(3, 50)  ← Called from multiple paths
│   │   ├── minCost(4, 50)
│   │   └── minCost(5, 50)
│   ├── minCost(3, 50)      ← Same call again!
│   └── minCost(4, 50)      ← Same call again!
├── minCost(2, 50)          ← Same call again!
└── minCost(3, 50)          ← Same call again!

Exponential explosion of redundant computations!

The Solution

JAVA(49 lines)
Code
Loading syntax highlighter...

The Impact

Metric	Before	After
50 warehouses	Timeout (>30s)	0.1ms
500 warehouses	Impossible	1ms
Peak hour failures	2,400/day	0
Route optimization	Disabled	Real-time

🧠 Mental Model: The Notebook Approach

Think of DP as a student solving math problems with a notebook:

┌─────────────────────────────────────────────────────────────────┐
│                    THE NOTEBOOK APPROACH                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  WITHOUT NOTEBOOK (Naive Recursion)                             │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │                                                         │    │
│  │  Teacher: "What's fib(5)?"                              │    │
│  │  Student: "I need fib(4) and fib(3)..."                 │    │
│  │                                                         │    │
│  │  Teacher: "What's fib(4)?"                              │    │
│  │  Student: "I need fib(3) and fib(2)..."                 │    │
│  │                                                         │    │
│  │  Teacher: "What's fib(3)?"  ← Asked AGAIN!              │    │
│  │  Student: Recalculates from scratch...                  │    │
│  │                                                         │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
│  WITH NOTEBOOK (Memoization)                                    │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │                                                         │    │
│  │  ┌─────────────────┐                                    │    │
│  │  │ NOTEBOOK        │                                    │    │
│  │  │ fib(1) = 1      │                                    │    │
│  │  │ fib(2) = 1      │                                    │    │
│  │  │ fib(3) = 2  ✓   │  ← Already calculated!             │    │ 
│  │  │ fib(4) = 3      │                                    │    │
│  │  │ fib(5) = 5      │                                    │    │
│  │  └─────────────────┘                                    │    │
│  │                                                         │    │
│  │  Teacher: "What's fib(3)?"                              │    │
│  │  Student: *checks notebook* "It's 2!"                   │    │
│  │                                                         │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Key insight: DP = Recursion + Memory

🔬 Deep Dive: Recognizing DP Problems

The Two Properties

1. Optimal Substructure

The optimal solution to the problem contains optimal solutions to subproblems.

JAVA(6 lines)
Code
Loading syntax highlighter...

2. Overlapping Subproblems

The same subproblems are solved multiple times.

JAVA(9 lines)
Code
Loading syntax highlighter...

When to Use DP vs Other Techniques

┌─────────────────────────────────────────────────────────────────┐
│                    TECHNIQUE SELECTION                          │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Problem has optimal substructure?                              │
│  ├── NO → Not suitable for DP                                   │
│  └── YES → Check for overlapping subproblems                    │
│            ├── NO → Use Divide & Conquer (no caching needed)    │
│            └── YES → Use Dynamic Programming                    │
│                                                                 │
│  Examples:                                                      │
│                                                                 │
│  MergeSort: Optimal substructure ✓, Overlapping ✗               │
│             → Divide & Conquer (subproblems are independent)    │
│                                                                 │
│  Fibonacci: Optimal substructure ✓, Overlapping ✓               │
│             → Dynamic Programming                               │
│                                                                 │
│  Greedy problems: Optimal substructure ✓, make local choice     │
│             → Greedy Algorithm (if greedy choice property)      │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: Memoization (Top-Down)

The Pattern

JAVA(23 lines)
Code
Loading syntax highlighter...

Fibonacci with Memoization

JAVA(21 lines)
Code
Loading syntax highlighter...

Climbing Stairs with Memoization

JAVA(18 lines)
Code
Loading syntax highlighter...

When to Use Memoization

Advantages:

Natural translation from recursive thinking
Only computes needed subproblems (lazy evaluation)
Easier to write initially

Disadvantages:

Recursion overhead (stack space)
Hash map overhead for complex states
Risk of stack overflow for deep recursion

🔬 Deep Dive: Tabulation (Bottom-Up)

The Pattern

JAVA(17 lines)
Code
Loading syntax highlighter...

Fibonacci with Tabulation

JAVA(33 lines)
Code
Loading syntax highlighter...

Climbing Stairs with Tabulation

JAVA(31 lines)
Code
Loading syntax highlighter...

When to Use Tabulation

Advantages:

No recursion overhead
Better cache locality
Easier to optimize space
No stack overflow risk

Disadvantages:

Must compute ALL subproblems (even unused ones)
Need to determine correct order of computation
Sometimes harder to visualize

🔬 Deep Dive: State Definition

The Most Critical Step

State definition is often the hardest part of DP. The state must:

Uniquely identify a subproblem
Be sufficient to compute the answer
Lead to a manageable number of states

Common State Patterns

JAVA(19 lines)
Code
Loading syntax highlighter...

Example: House Robber

Problem: Rob houses for maximum money, can't rob adjacent houses.

JAVA(40 lines)
Code
Loading syntax highlighter...

Example: Coin Change

Problem: Minimum coins to make amount.

JAVA(34 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Writing Recurrence Relations

The Formula Approach

Define what dp[state] represents
Identify choices at each state
Write recurrence based on choices
Identify base cases

Example: Minimum Path Sum

JAVA(34 lines)
Code
Loading syntax highlighter...

Example: Unique Paths

JAVA(40 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Wrong Base Case

JAVA(21 lines)
Code
Loading syntax highlighter...

Mistake 2: Wrong Iteration Order

JAVA(9 lines)
Code
Loading syntax highlighter...

Mistake 3: Off-by-One in Array Size

JAVA(7 lines)
Code
Loading syntax highlighter...

Mistake 4: Modifying Memo During Recursion

JAVA(24 lines)
Code
Loading syntax highlighter...

🐛 Debug This: Incorrect State Transition

This climbing stairs solution has a bug. Can you find it?

JAVA(20 lines)
Code
Loading syntax highlighter...

🔍 Click to reveal the bug

Bug: The transition doesn't account for 3-step jumps.

JAVA(5 lines)
Code
Loading syntax highlighter...

The problem states you can take 1, 2, or 3 steps, but the transition only considers 1 and 2 steps.

Example for n=4:

Bug returns: 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
Correct: 7 (adds 1+3, 3+1)

💻 Exercises

Exercise 1: Jump Game ⭐⭐

Given array where nums[i] is max jump length from position i, determine if you can reach the last index.

JAVA(4 lines)
Code
Loading syntax highlighter...

Exercise 2: Decode Ways ⭐⭐

Count ways to decode a digit string into letters (A=1, B=2, ..., Z=26).

JAVA(4 lines)
Code
Loading syntax highlighter...

Example: "226" → 3 ways: "BZ" (2,26), "VF" (22,6), "BBF" (2,2,6)

Exercise 3: Maximum Subarray ⭐⭐

Find contiguous subarray with largest sum (Kadane's algorithm as DP).

JAVA(4 lines)
Code
Loading syntax highlighter...

Exercise 4: Word Break ⭐⭐⭐

Given string s and dictionary, determine if s can be segmented into dictionary words.

JAVA(4 lines)
Code
Loading syntax highlighter...

Exercise 5: Palindrome Partitioning ⭐⭐⭐⭐

Find minimum cuts to partition string into palindromes.

JAVA(5 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Q1: "How do you decide between memoization and tabulation?"

Answer:

Factor	Memoization	Tabulation
Ease of implementation	Easier (natural recursion)	Requires understanding order
Subproblems computed	Only needed ones	All subproblems
Stack space	O(recursion depth)	O(1) extra
Cache performance	Worse (scattered access)	Better (sequential)
Space optimization	Harder	Easier

My approach:

Start with memoization for quick solution
Convert to tabulation if needed for performance
Optimize space if only recent states matter

Q2: "Walk me through solving a DP problem."

Answer: I use a systematic 5-step approach:

Step 1: RECOGNIZE
- Does it have optimal substructure?
- Are there overlapping subproblems?
- Can I solve smaller versions first?

Step 2: DEFINE STATE
- What information do I need to uniquely identify a subproblem?
- What does dp[state] represent?

Step 3: WRITE RECURRENCE
- What choices do I have at each state?
- How do I combine subproblem solutions?

Step 4: IDENTIFY BASE CASES
- What are the smallest subproblems?
- What are their answers?

Step 5: DETERMINE ORDER
- Which subproblems depend on which?
- Fill table in correct order

Q3: "How would you optimize this DP from O(n²) space to O(n)?"

Answer: Look at the recurrence to see which previous states are needed:

JAVA(27 lines)
Code
Loading syntax highlighter...

Q4: "What's the difference between DP and greedy?"

Answer:

Dynamic Programming:
- Considers ALL choices at each step
- Guaranteed optimal solution
- Higher time complexity
- Example: 0/1 Knapsack

Greedy:
- Makes LOCALLY optimal choice
- May not be globally optimal
- Lower time complexity
- Example: Fractional Knapsack

When greedy works:
- Greedy choice property: local optimum leads to global optimum
- Optimal substructure: still needed

Example where greedy fails:
Coins [1, 3, 4], Amount = 6
Greedy: 4 + 1 + 1 = 3 coins
Optimal: 3 + 3 = 2 coins

Q5: "How do you handle DP problems with multiple constraints?"

Answer: Add dimensions to the state:

JAVA(12 lines)
Code
Loading syntax highlighter...

Example: Knapsack with capacity AND item count limit:

JAVA(21 lines)
Code
Loading syntax highlighter...

📋 Quick Reference

DP Problem Categories

Category	State	Example
Linear	dp[i]	Climbing stairs, House robber
2D Grid	dp[i][j]	Unique paths, Min path sum
Interval	dp[i][j] for [i,j]	Matrix chain, Palindrome
Knapsack	dp[i][w]	0/1 Knapsack, Coin change
String	dp[i][j]	LCS, Edit distance
Bitmask	dp[mask]	TSP, Subset problems

Complexity Patterns

dp[n]           → O(n) time, O(n) or O(1) space
dp[n][m]        → O(nm) time, O(nm) or O(m) space
dp[n][n]        → O(n²) time, O(n²) or O(n) space
dp[2^n]         → O(2^n) time, O(2^n) space
dp[n][2^n]      → O(n × 2^n) time and space

Key Code Patterns

JAVA(19 lines)
Code
Loading syntax highlighter...

🔗 What's Next?

In Part 17: Classic DP Patterns, we'll explore:

0/1 Knapsack and variants
Longest Common Subsequence (LCS)
Longest Increasing Subsequence (LIS)
Edit Distance (Levenshtein)
Matrix Chain Multiplication

📅 Review Schedule

Day	Focus	Time
0	Full read + exercises 1-2	90 min
1	Quick Reference review	10 min
3	Implement Fibonacci both ways	15 min
7	Exercises 3-4	30 min
14	Debug exercise + Exercise 5	20 min
30	Interview questions	15 min

Next: Part 17: Classic DP Patterns →

Series: Algorithms Compendium Index

Dynamic Programming Foundations

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Shipping Cost Disaster

The Problem

The Investigation

The Solution

The Impact

🧠 Mental Model: The Notebook Approach

🔬 Deep Dive: Recognizing DP Problems

The Two Properties

When to Use DP vs Other Techniques

🔬 Deep Dive: Memoization (Top-Down)

The Pattern

Fibonacci with Memoization

Climbing Stairs with Memoization

When to Use Memoization

🔬 Deep Dive: Tabulation (Bottom-Up)

The Pattern

Fibonacci with Tabulation

Climbing Stairs with Tabulation

When to Use Tabulation

🔬 Deep Dive: State Definition

The Most Critical Step

Common State Patterns

Example: House Robber

Example: Coin Change

🔬 Deep Dive: Writing Recurrence Relations

The Formula Approach

Example: Minimum Path Sum

Example: Unique Paths

⚠️ Common Mistakes

Mistake 1: Wrong Base Case

Mistake 2: Wrong Iteration Order

Mistake 3: Off-by-One in Array Size

Mistake 4: Modifying Memo During Recursion

🐛 Debug This: Incorrect State Transition

💻 Exercises

Exercise 1: Jump Game ⭐⭐

Exercise 2: Decode Ways ⭐⭐

Exercise 3: Maximum Subarray ⭐⭐

Exercise 4: Word Break ⭐⭐⭐

Exercise 5: Palindrome Partitioning ⭐⭐⭐⭐

🎤 Interview Questions

Q1: "How do you decide between memoization and tabulation?"

Q2: "Walk me through solving a DP problem."

Q3: "How would you optimize this DP from O(n²) space to O(n)?"

Q4: "What's the difference between DP and greedy?"

Q5: "How do you handle DP problems with multiple constraints?"

📋 Quick Reference

DP Problem Categories

Complexity Patterns

Key Code Patterns

🔗 What's Next?

📅 Review Schedule

Tags: