Classic DP Patterns

📋 At a Glance

Aspect	Details
Time to Read	40 minutes
Prerequisites	Part 16 (DP Foundations)
Key Concepts	Knapsack, LCS, LIS, Edit Distance, Matrix Chain
Difficulty	⭐⭐⭐ (Intermediate)

┌─────────────────────────────────────────────────────────────────┐
│                  CLASSIC DP PATTERNS                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  KNAPSACK FAMILY              SEQUENCE PROBLEMS                 │
│  ┌─────────────────┐          ┌─────────────────┐               │
│  │ 0/1 Knapsack    │          │ LCS             │               │
│  │ ─────────────── │          │ ─────────────── │               │
│  │ Take or leave   │          │ Match chars     │               │
│  │ each item       │          │ in both strings │               │
│  │                 │          │                 │               │
│  │ Unbounded       │          │ LIS             │               │
│  │ ─────────────── │          │ ─────────────── │               │
│  │ Unlimited copies│          │ Increasing      │               │
│  │ of each item    │          │ subsequence     │               │
│  └─────────────────┘          └─────────────────┘               │
│                                                                 │
│  STRING OPERATIONS            OPTIMIZATION                      │
│  ┌─────────────────┐          ┌─────────────────┐               │
│  │ Edit Distance   │          │ Matrix Chain    │               │
│  │ ─────────────── │          │ ─────────────── │               │
│  │ Insert, Delete  │          │ Optimal         │               │
│  │ Replace         │          │ parenthesization│               │
│  │                 │          │                 │               │
│  │ Used in: diff,  │          │ Used in:        │               │
│  │ spell check,    │          │ query planning, │               │
│  │ DNA alignment   │          │ expression eval │               │
│  └─────────────────┘          └─────────────────┘               │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

Solve knapsack variants: 0/1, unbounded, bounded, subset sum
Find LCS: Longest common subsequence between strings
Compute LIS: Longest increasing subsequence in O(n log n)
Calculate edit distance: Transform one string to another
Optimize matrix chains: Find optimal multiplication order

🔥 Production Story: The Code Review Diff Engine

A code review platform needed to show differences between file versions. Their naive diff algorithm was timing out on large files.

The Problem

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

Files with 10,000 lines were timing out after 30 seconds.

The Solution: LCS-Based Diff

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

The Impact

File Size	Before	After
100 lines	50ms	2ms
1,000 lines	5s	20ms
10,000 lines	Timeout	200ms
100,000 lines	Impossible	2s

🔬 Deep Dive: 0/1 Knapsack

The Problem

Given items with weights and values, maximize value within weight capacity.

🎮 Try It Yourself

Watch how the DP table fills up step by step:

0/1 Knapsack (Dynamic Programming)
Time: O(nW)Space: O(nW)
1 / 34
Initialize DP table: 5 rows (items) × 9 cols (capacity). Base case: dp[0][*] = 0
DP problems:Knapsack, LCS, edit distance, coin change, shortest paths
Key insight:Optimal substructure + overlapping subproblems = memoize!
DP Recurrence Formula
dp[i][w] = max( skip, take)
skip = dp[i-1][w]Don't take item i
take = dp[i-1][w-weight] + valueTake item i
Current cell calculation will appear here...
Items (i = item index):
i=1: w=2, v=3
i=2: w=3, v=4
i=3: w=4, v=5
i=4: w=5, v=6
Max Capacity: 8
DP Table (w = current capacity):
i\w 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
Pseudocode
1for i = 1 to n:
2  for w = 1 to capacity:
3    if item[i].weight > w:
4      dp[i][w] = dp[i-1][w]
5    else:
6      skip = dp[i-1][w]
7      take = dp[i-1][w-weight] + value
8      dp[i][w] = max(skip, take)
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Not computed
Not computed
Computed
Computed
Take item
Take item
Skip item
Skip item
P · [ ] · R
Loading visualizer...

i\w	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0

Visual Representation

┌─────────────────────────────────────────────────────────────────┐
│                    0/1 KNAPSACK                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Items:     [📱, 💻, 📷, 🎧]                                   │
│  Weights:   [1,  4,  3,  2]                                     │
│  Values:    [15, 30, 20, 10]                                    │
│  Capacity:  5                                                   │
│                                                                 │
│  State: dp[i][w] = max value using items 0..i-1 with capacity w │
│                                                                 │
│  Transition:                                                    │
│  dp[i][w] = max(                                                │
│      dp[i-1][w],              // Don't take item i              │
│      dp[i-1][w-wt[i]] + val[i] // Take item i (if fits)         │
│  )                                                              │
│                                                                 │
│  Answer: dp[n][W] = 35 (take 📱 and 💻: weights 1+4=5)          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

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

Knapsack Variants

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

🔬 Deep Dive: Longest Common Subsequence (LCS)

The Problem

Find the longest sequence present in both strings (not necessarily contiguous).

┌─────────────────────────────────────────────────────────────────┐
│                    LCS VISUALIZATION                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  String A: A B C D G H                                          │
│  String B: A E D F H R                                          │
│                                                                 │
│  LCS:      A     D   H    (length = 3)                          │
│            ↑     ↑   ↑                                          │
│                                                                 │
│  State: dp[i][j] = LCS length for A[0..i-1] and B[0..j-1]       │
│                                                                 │
│  Transition:                                                    │
│  if A[i-1] == B[j-1]:                                           │
│      dp[i][j] = dp[i-1][j-1] + 1    // Match! Extend LCS        │
│  else:                                                          │
│      dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // Skip one char   │
│                                                                 │
│          ""  A  E  D  F  H  R                                   │
│      ""   0  0  0  0  0  0  0                                   │
│      A    0  1  1  1  1  1  1                                   │
│      B    0  1  1  1  1  1  1                                   │
│      C    0  1  1  1  1  1  1                                   │
│      D    0  1  1  2  2  2  2                                   │
│      G    0  1  1  2  2  2  2                                   │
│      H    0  1  1  2  2  3  3  ← Answer                         │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

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

LCS Variants

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

🔬 Deep Dive: Longest Increasing Subsequence (LIS)

The Problem

Find the longest strictly increasing subsequence.

┌─────────────────────────────────────────────────────────────────┐
│                    LIS EXAMPLE                                  │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Array: [10, 9, 2, 5, 3, 7, 101, 18]                            │
│                                                                 │
│  LIS:   [    2,    3, 7,      18]   (length = 4)                │
│  or:    [    2, 5,    7,      18]   (also length 4)             │
│                                                                 │
│  O(n²) DP State:                                                │
│  dp[i] = LIS length ending at index i                           │
│                                                                 │
│  Transition:                                                    │
│  dp[i] = 1 + max(dp[j]) for all j < i where arr[j] < arr[i]     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

O(n²) Implementation

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

O(n log n) Binary Search Solution

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

LIS Variants

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

🔬 Deep Dive: Edit Distance (Levenshtein)

The Problem

Minimum operations to transform one string to another.

┌─────────────────────────────────────────────────────────────────┐
│                    EDIT DISTANCE                                │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Transform "horse" → "ros"                                      │
│                                                                 │
│  Operations:                                                    │
│  horse → rorse (replace 'h' with 'r')                           │
│  rorse → rose  (delete 'r')                                     │
│  rose  → ros   (delete 'e')                                     │
│                                                                 │
│  Edit distance = 3                                              │
│                                                                 │
│  State: dp[i][j] = edit distance for s1[0..i-1] and s2[0..j-1]  │
│                                                                 │
│  Transition:                                                    │
│  if s1[i-1] == s2[j-1]:                                         │
│      dp[i][j] = dp[i-1][j-1]           // No operation needed   │
│  else:                                                          │
│      dp[i][j] = 1 + min(                                        │
│          dp[i-1][j-1],  // Replace                              │
│          dp[i-1][j],    // Delete from s1                       │
│          dp[i][j-1]     // Insert into s1                       │
│      )                                                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

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

Edit Distance Variants

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

🔬 Deep Dive: Matrix Chain Multiplication

The Problem

Find the optimal way to parenthesize matrix multiplication to minimize operations.

┌─────────────────────────────────────────────────────────────────┐
│              MATRIX CHAIN MULTIPLICATION                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Matrices: A(10×30) × B(30×5) × C(5×60)                         │
│                                                                 │
│  Option 1: (A × B) × C                                          │
│    A × B = 10×30×5 = 1500 ops → result 10×5                     │
│    (AB) × C = 10×5×60 = 3000 ops                                │
│    Total: 4500 ops                                              │
│                                                                 │
│  Option 2: A × (B × C)                                          │
│    B × C = 30×5×60 = 9000 ops → result 30×60                    │
│    A × (BC) = 10×30×60 = 18000 ops                              │
│    Total: 27000 ops                                             │
│                                                                 │
│  Optimal: Option 1 (6× faster!)                                 │
│                                                                 │
│  State: dp[i][j] = min cost to multiply matrices i to j         │
│                                                                 │
│  Transition:                                                    │
│  dp[i][j] = min over k of:                                      │
│      dp[i][k] + dp[k+1][j] + dims[i-1] × dims[k] × dims[j]      │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

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

⚠️ Common Mistakes

Mistake 1: Knapsack Wrong Direction

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

Mistake 2: LCS Off-by-One

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

Mistake 3: Edit Distance Missing Base Cases

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

🐛 Debug This: LIS Binary Search Bug

This O(n log n) LIS implementation has a bug. Can you find it?

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

🔍 Click to reveal the bug

Bug: Using <= instead of < in comparison.

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

With <=, equal elements are placed after existing elements, allowing duplicates in the subsequence. For strictly increasing LIS, we need <.

Example:

Input: [1, 3, 3, 5]
Bug answer: 4 (allows [1, 3, 3, 5])
Correct: 3 ([1, 3, 5])

💻 Exercises

Exercise 1: Target Sum ⭐⭐

Given array and target, assign + or - to each element to reach target. Count ways.

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

Exercise 2: Longest Palindromic Substring ⭐⭐

Find the longest palindromic substring (contiguous).

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

Exercise 3: Distinct Subsequences ⭐⭐⭐

Count distinct subsequences of s that equal t.

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

Exercise 4: Interleaving String ⭐⭐⭐

Check if s3 is formed by interleaving s1 and s2.

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

Exercise 5: Burst Balloons ⭐⭐⭐⭐

Burst balloons to maximize coins (similar to matrix chain).

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

🎤 Interview Questions

Q1: "Explain the difference between LCS and LIS."

Answer:

Aspect	LCS	LIS
Input	Two sequences	One sequence
Goal	Longest common to both	Longest increasing
State	dp[i][j] - 2D	dp[i] - 1D
Time	O(nm)	O(n²) or O(n log n)
Application	Diff, DNA alignment	Patience sorting

Key insight: LCS finds matching elements between sequences; LIS finds ordered elements within one sequence.

Q2: "How would you optimize 0/1 Knapsack for very large capacity?"

Answer: Several approaches depending on constraints:

Meet in the middle (if n ≤ 40):
- Split items into two halves
- Enumerate all 2^(n/2) combinations for each
- Use binary search to find best complement
- O(2^(n/2) × n) instead of O(nW)
If values are small (sum of values ≤ V):
- dp[v] = minimum weight to achieve value v
- O(nV) instead of O(nW)
Sparse DP (if few distinct weights):
- Use HashMap instead of array
- Only store reachable states

Q3: "When would edit distance give wrong results for spell checking?"

Answer: Edit distance has limitations:

Doesn't consider keyboard layout:
- "teh" → "the" (2 edits)
- But they're adjacent keys - should be weighted lower
Ignores phonetics:
- "knight" vs "nite" (4 edits)
- But they sound the same
Equal cost for all operations:
- Transposition ("hte" → "the") costs 2 but is a common typo

Better approaches:

Damerau-Levenshtein (adds transposition)
Weighted edit distance (keyboard-aware)
Soundex/Metaphone (phonetic matching)

Answer: The O(n log n) LIS algorithm is essentially patience sorting:

Patience sorting:
- Deal cards into piles
- Each pile is descending
- Place card on leftmost pile where it fits
- Number of piles = LIS length

LIS algorithm:
- tails[i] = smallest ending element of LIS length i+1
- Binary search to find where new element goes
- Same as finding which pile to place card

This connection shows:
1. LIS can be found in O(n log n)
2. Patience sorting produces an optimal LIS
3. The algorithm is actually a greedy approach

Q5: "How would you find all LCS strings, not just length?"

Answer:

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

Caution: Can be exponential in number of LCS strings!

📋 Quick Reference

Pattern Recognition

Problem Type	State	Transition
0/1 Knapsack	dp[i][w]	max(skip, take)
Unbounded Knapsack	dp[w]	max over all items
LCS	dp[i][j]	match or max(skip)
LIS	dp[i]	max(dp[j]+1) for j<i, a[j]<a[i]
Edit Distance	dp[i][j]	match or 1+min(ops)
Matrix Chain	dp[i][j]	min over split point

Complexity Summary

Algorithm	Time	Space (Optimized)
0/1 Knapsack	O(nW)	O(W)
LCS	O(nm)	O(min(n,m))
LIS	O(n log n)	O(n)
Edit Distance	O(nm)	O(min(n,m))
Matrix Chain	O(n³)	O(n²)

Key Code Patterns

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

🔗 What's Next?

In Part 18: Advanced DP Techniques, we'll explore:

DP on trees
Bitmask DP
Digit DP
Convex hull trick
Space optimization techniques

📅 Review Schedule

Day	Focus	Time
0	Full read + Knapsack exercise	90 min
1	Quick Reference	10 min
3	Implement LCS from memory	20 min
7	LIS + Edit Distance exercises	30 min
14	Debug exercise + Matrix Chain	20 min
30	All interview questions	15 min

Next: Part 18: Advanced DP Techniques →

Series: Algorithms Compendium Index

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Code Review Diff Engine

The Problem

The Solution: LCS-Based Diff

The Impact

🔬 Deep Dive: 0/1 Knapsack

The Problem

🎮 Try It Yourself

0/1 Knapsack (Dynamic Programming)

Visual Representation

Implementation

Knapsack Variants

🔬 Deep Dive: Longest Common Subsequence (LCS)

The Problem

Implementation

LCS Variants

🔬 Deep Dive: Longest Increasing Subsequence (LIS)

The Problem

O(n²) Implementation

O(n log n) Binary Search Solution

LIS Variants

🔬 Deep Dive: Edit Distance (Levenshtein)

The Problem

Implementation

Edit Distance Variants

🔬 Deep Dive: Matrix Chain Multiplication

The Problem

Implementation

⚠️ Common Mistakes

Mistake 1: Knapsack Wrong Direction

Mistake 2: LCS Off-by-One

Mistake 3: Edit Distance Missing Base Cases

🐛 Debug This: LIS Binary Search Bug

💻 Exercises

Exercise 1: Target Sum ⭐⭐

Exercise 2: Longest Palindromic Substring ⭐⭐

Exercise 3: Distinct Subsequences ⭐⭐⭐

Exercise 4: Interleaving String ⭐⭐⭐

Exercise 5: Burst Balloons ⭐⭐⭐⭐

🎤 Interview Questions

Q1: "Explain the difference between LCS and LIS."

Q2: "How would you optimize 0/1 Knapsack for very large capacity?"

Q3: "When would edit distance give wrong results for spell checking?"

Q4: "How is LIS related to patience sorting?"

Q5: "How would you find all LCS strings, not just length?"

📋 Quick Reference

Pattern Recognition

Complexity Summary

Key Code Patterns

🔗 What's Next?

📅 Review Schedule

Tags:

0/1 Knapsack (Dynamic Programming)