Repository Guide | English | 한국어
Last Updated: 2026-11-18
Learning Objectives:
- Compare naive recursion, memoization, and tabulation through the Fibonacci problem
- Build a 2D DP table for LCS and recover the actual subsequence via traceback
- Implement the 0-1 Knapsack problem with DP and trace selected items
- Experience how LCS-based diff is applied in a real web application
- 1. Overview
- 2. Type A: Algorithm Implementation
- 3. Type B: Web Code Analysis
- 4. The DP Recipe
- Summary
- Self-Check Questions
- Understand and implement the core DP patterns, memoization and tabulation.
- Build a 2D DP table for LCS and recover the actual subsequence via traceback.
- Implement the 0-1 Knapsack problem with DP and trace selected items through traceback.
- Analyze how LCS-based diff is used in a real web application.
| Section | Topic |
|---|---|
| A-1 | Fibonacci Comparison |
| A-2 | LCS and DP Table Visualization |
| A-3 | 0-1 Knapsack and Traceback |
| B-1 | Text Diff Viewer |
Table 1. Topic of each lab section
The Type A code uses only the standard library, so no external packages are required; Flask is needed only for B-1.
Compare three approaches to computing Fibonacci numbers and observe how DP eliminates redundant computation.
Goal: Compute the same Fibonacci numbers in three ways and compare their measured running times.
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2
Reason naive recursion is so slow
graph TD
f5["F(5)"] --> f4["F(4)"]
f5 --> f3a["F(3)"]
f4 --> f3b["F(3)"]
f4 --> f2a["F(2)"]
f3a --> f2b["F(2)"]
f3a --> f1a["F(1)"]
f3b --> f2c["F(2)"]
f3b --> f1b["F(1)"]
f2c --> f1c["F(1)"]
f2c --> f0["F(0)"]
f2a --> e1["..."]
f2b --> e2["..."]
Figure 1. Call tree of naive recursion computing F(5)
Overlapping subproblems appear: F(3) is computed 2 times and F(2) 3 times, so the total number of calls for F(n) is O(2^n).
# 1. Naive recursion: O(2^n) — exponentially slow
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# 2. Memoization (top-down): O(n) — cache results
def fib_memo(n, memo=None):
if memo is None: memo = {}
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
# 3. Tabulation (bottom-up): O(n) — fill table iteratively
def fib_tab(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n] N | Naive | Memo | Tabulation
------+--------------+----------------+----------------
10 | 0.000005s | 0.000003s | 0.000002s
20 | 0.001200s | 0.000004s | 0.000002s
30 | 0.150000s | 0.000005s | 0.000003s
35 | 1.800000s | 0.000005s | 0.000003s
40 | too slow | 0.000006s | 0.000003s
The measurements are approximate and vary with the execution environment.
Key comparison:
| Approach | Time | Space | Direction |
|---|---|---|---|
| Naive recursion | O(n) stack | N/A | |
| Memoization | O(n) | O(n) cache + stack | Top-down |
| Tabulation | O(n) | O(n) table | Bottom-up |
Table 2. Time, space, and direction of the three Fibonacci approaches
Memoization is recursion plus caching, and tabulation is iterative table filling. Both eliminate overlapping subproblems, and tabulation also avoids recursion overhead.
Problem: Find the longest common subsequence (LCS) of two strings.
A subsequence preserves order but not necessarily contiguity.
X = "ABCBDAB"
Y = "BDCAB"
Common subsequences: "B", "AB", "BD", "BCB", "BCAB", ...
Longest: "BCAB" (length 4)
X: A B C B D A B
^ ^ ^ ^
Y: B D C A B
^ ^ ^ ^
Figure 2. Common subsequences of X and Y with the positions of LCS characters marked
Recurrence:
If X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1 (match!)
If X[i] != Y[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Time: O(m × n), Space: O(m × n)
X = "ABCBDAB", Y = "BDCAB"
"" B D C A B
0 1 2 3 4 5
----------------------------------
"" 0 | 0 0 0 0 0 0
A 1 | 0 0 0 0 1 1
B 2 | 0 [1] (1) 1 1 2
C 3 | 0 1 1 [2] 2 2
B 4 | 0 1 1 (2) 2 3
D 5 | 0 1 2 (2) 2 3
A 6 | 0 1 2 2 [3] 3
B 7 | 0 1 2 2 3 [4]
[n] = match (diagonal move, included in LCS)
(n) = traceback path
Figure 3. LCS DP table for X = ABCBDAB and Y = BDCAB
LCS = BCAB (length 4)
def build_lcs_table(x, y):
"""
Build the LCS DP table.
dp[i][j] = length of LCS of X[0..i-1] and Y[0..j-1]
Time complexity: O(m * n)
Space complexity: O(m * n)
"""
m, n = len(x), len(y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp
def backtrack_lcs(dp, x, y):
"""
Recover the actual LCS string by backtracking through the DP table.
Start at dp[m][n] and trace back to dp[0][0].
"""
lcs = []
i, j = len(x), len(y)
while i > 0 and j > 0:
if x[i - 1] == y[j - 1]:
lcs.append(x[i - 1])
i -= 1; j -= 1 # diagonal
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1 # up
else:
j -= 1 # left
return "".join(reversed(lcs))Start at dp[7][5] = 4, trace back to dp[0][0]:
(7,5): X[7]='B' == Y[5]='B' -> diagonal (MATCH: 'B')
(6,4): X[6]='A' == Y[4]='A' -> diagonal (MATCH: 'A')
(5,3): X[5]='D' != Y[3]='C' -> up (dp[4][3]=2 >= dp[5][2]=2)
(4,3): X[4]='B' != Y[3]='C' -> up (dp[3][3]=2 >= dp[4][2]=1)
(3,3): X[3]='C' == Y[3]='C' -> diagonal (MATCH: 'C')
(2,2): X[2]='B' != Y[2]='D' -> left (dp[1][2]=0 < dp[2][1]=1)
(2,1): X[2]='B' == Y[1]='B' -> diagonal (MATCH: 'B')
Collected (reversed): B -> C -> A -> B = "BCAB"
Applications of LCS:
- git diff: compares file versions line by line.
- DNA sequence alignment: compares genetic sequences.
- Edit distance: finds the minimum number of edits to transform one string into another.
Problem: Select items to maximize value without exceeding capacity. Items cannot be split, so each is either taken whole or left.
Capacity: 50
Item Value Weight
--------------------------
Laptop 60 10
Camera 100 20
Painting 120 30
Book 40 5
Recurrence:
dp[i][j] = maximum value using first i items with capacity j
If weight_i > j: dp[i][j] = dp[i-1][j] (can't take item i)
Otherwise: dp[i][j] = max(
dp[i-1][j], (skip item i)
dp[i-1][j - weight_i] + v_i (take item i)
)
Which items should we pick?
Capacity -> 0 5 10 15 20 25 30 35 40 45 50
---------------------------------------------------------
(none) 0 | 0 0 0 0 0 0 0 0 0 0 0
Laptop 1 | 0 0 60 60 60 60 60 60 60 60 60
Camera 2 | 0 0 60 60 100 100 160 160 160 160 160
Paint. 3 | 0 0 60 60 100 100 160 160 180 180 220
Book 4 | 0 40 60 100 100 140 160 200 200 220 220
Answer: dp[4][50] = 220
Trace back from dp[4][50]:
dp[4][50]=220 == dp[3][50]=220 -> skip Book
dp[3][50]=220 != dp[2][50]=160 -> TAKE Painting (j: 50->20)
dp[2][20]=100 != dp[1][20]=60 -> TAKE Camera (j: 20->0)
dp[1][0]=0 == dp[0][0]=0 -> skip Laptop
Selected: Camera (100, 20kg) + Painting (120, 30kg) = 220
Figure 4. DP table and traceback for the 0-1 knapsack example with capacity 50
Note: Another optimal solution. Laptop + Painting + Book (weight 45, value 220) is another optimal solution with the same maximum value. The code in Section 2.3.3 skips an item when dp[i][j] = dp[i-1][j], so it picks Camera + Painting.
def knapsack_01(capacity, items):
"""
Solve the 0-1 knapsack problem using DP.
items: list of (value, weight, name)
Returns: max value, selected items.
Time complexity: O(n * W)
Space complexity: O(n * W) (W = capacity)
"""
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
v, w, _ = items[i - 1]
for j in range(capacity + 1):
dp[i][j] = dp[i - 1][j] # skip
if w <= j and dp[i - 1][j - w] + v > dp[i][j]:
dp[i][j] = dp[i - 1][j - w] + v # take
# Backtrack to find selected items
selected = []
j = capacity
for i in range(n, 0, -1):
if dp[i][j] != dp[i - 1][j]:
selected.append(items[i - 1])
j -= items[i - 1][1] # subtract weight
return dp[n][capacity], list(reversed(selected))Time: O(n × W), Space: O(n × W) (W = capacity)
Install dependencies first with pip install flask, then run the Flask app.
Enter two texts and the app highlights the differences based on LCS.
Text A: "The quick brown fox"
Text B: "The slow brown dog"
Diff output:
"The "
[-quick-] [+slow+]
" brown "
[-fox-] [+dog+]
This is the same principle behind GitHub's diff feature.
1. Split texts into tokens (words or lines)
2. Compute LCS of the two token sequences
3. Tokens in LCS -> unchanged (white)
Tokens only in A -> deleted (red)
Tokens only in B -> inserted (green)
Text A tokens: [The, quick, brown, fox]
Text B tokens: [The, slow, brown, dog]
LCS: [The, brown]
Alignment:
The The <- same (LCS)
quick --- <- deleted
--- slow <- inserted
brown brown <- same (LCS)
fox --- <- deleted
--- dog <- inserted
Figure 5. Processing steps and token alignment of LCS-based diff
Experiment:
- Try short sentences with a few word changes.
- Try longer paragraphs and observe how LCS captures the common structure.
- Consider why this approach is O(m × n), where m and n are the token counts.
Design a DP algorithm in the following five steps.
1. Define the subproblem — what does dp[i][j] represent?
2. Write the recurrence — how does dp[i][j] relate to smaller subproblems?
3. Identify base cases — dp[0][...] = ?, dp[...][0] = ?
4. Determine fill order — usually left-to-right, top-to-bottom
5. Trace back if needed — recover the actual solution, not just the value
| Concept | Key Summary |
|---|---|
| Fibonacci | Naive recursion takes |
| LCS | A 2D DP table is filled and then traceback recovers the actual subsequence. |
| 0-1 Knapsack | The DP table is built and traceback finds the selected items. |
| Text Diff | It applies LCS to a real web application and works on the same principle as GitHub diff. |
| DP recipe | A DP is designed by defining the subproblem, writing the recurrence, identifying base cases, determining the fill order, and tracing back when needed. |
-
Why does naive recursion for Fibonacci have
$O(2^n)$ time complexity? Draw the recursion tree for F(5) and count how many times F(2) is computed.Answer
Each call branches into two recursive calls and the recursion depth is at most
$n$ , so the call tree has at most about$2^n$ nodes. The tree is not balanced, because the right branch is shorter, so the exact number of calls grows as$\Theta(\phi^n)$ with$\phi \approx 1.618$ . The same subproblem is recomputed across many branches: inF(5)the call tree hasF(5) → F(4), F(3);F(4) → F(3), F(2); both copies ofF(3) → F(2), F(1). Counting all leaves under those branches, F(2) is computed 3 times (and F(1) 5 times, F(0) 3 times). The redundancy grows exponentially with$n$ , which gives the$O(2^n)$ bound. -
In the LCS problem, what is the role of the traceback step? Why is the final value dp[m][n] alone not enough to determine the actual subsequence?
Answer
The DP table stores only the length of the LCS at each cell, not which characters were chosen. Many different subsequences can produce the same length, so
dp[m][n] = 4tells us the LCS is 4 characters but not which 4. Traceback walks the table fromdp[m][n]back todp[0][0], replaying the decision at each cell: on a match (X[i] == Y[j]) it emits the character and moves diagonally; otherwise it steps in the direction of the larger neighbor. Each step is$O(1)$ , so reconstruction adds only$O(m+n)$ to the algorithm. -
For the 0-1 Knapsack example, why is the Book (value 40, weight 5) not selected even though it has the best value/weight ratio (8.0/kg)?
Answer
0-1 Knapsack is not solved by greedy ratio selection because items are indivisible. Taking items in ratio order picks Book (8.0/kg), Laptop (6.0/kg), and Camera (5.0/kg), reaching only value 200 at weight 35, and Painting no longer fits. Camera (100, 20) + Painting (120, 30) fills the bag exactly to 50 with value 220. Another optimal solution, Laptop + Painting + Book (weight 45), also reaches 220, so the Book is not excluded from every optimum. The traceback in Section 2.3.3 sees dp[4][50] = dp[3][50] = 220, meaning the maximum is reachable without the Book, and skips it. DP compares all subset combinations implicitly, so it recognizes that the combined value of an item combination beats the ratio-first choice.
-
How does the text diff viewer use LCS? Explain why this approach is O(m × n) and what happens when texts are very long.
Answer
The two texts are tokenized (by word or line), and LCS over the token sequences identifies the longest aligned common run. Tokens inside the LCS are unchanged, tokens only in A are deletions, tokens only in B are insertions. Building the LCS table is
$O(m \times n)$ because every cell is filled in$O(1)$ time. For very long texts this becomes problematic: a 10,000-line vs 10,000-line diff requires$10^8$ cells and as much memory. Production tools (likegit diff) use Myers' diff algorithm ($O((m+n)D)$ where$D$ is edit distance) and Hunt-McIlroy-style optimizations to do much better in practice. -
Compare memoization and tabulation: when would you prefer one over the other? Consider stack depth, ease of implementation, and cache efficiency.
Answer
Memoization is easier to write, since you add a cache check to the natural recursive definition, and it only solves subproblems actually reached, which helps when the state space is sparse. Its downsides are recursion overhead and stack depth limits (Python defaults to about 1000 frames; deep DP recurrences exceed the limit without
sys.setrecursionlimit). Tabulation iterates in dependency order, avoiding recursion entirely; it has lower constant factors, better cache locality (sequential memory access), and can be space-optimized to$O(1)$ rows. Prefer memoization for sparsely needed states or complex recurrences; prefer tabulation when performance matters and most states are needed. -
In the DP recipe, why does fill order matter? What would happen if you tried to fill the LCS table from bottom-right to top-left?
Answer
Fill order must respect the dependency direction of the recurrence: every cell needs its inputs already computed. The LCS recurrence reads
dp[i-1][j-1],dp[i-1][j], anddp[i][j-1], so filling left-to-right and top-to-bottom guarantees those are ready. Reversing to bottom-right → top-left reads cells that have not yet been computed; they still hold initialization values (0), producing garbage. To go in reverse, you would need to redefinedp[i][j]as the LCS of the suffixesX[i..m]andY[j..n]with the dependencies flipped accordingly.