Fibonacci and Linear DP: Starting with Simple One-Dimensional Problems
Learning Objectives: By the end of this lesson, you will be able to:
- Master the classic Fibonacci problem and its variations
- Understand linear DP patterns and state transitions
- Implement space-optimized solutions for one-dimensional DP problems
- Recognize when problems follow linear DP patterns
- Apply linear DP techniques to solve related counting and optimization problems
1. Welcome and Introduction (5 minutes)
Icebreaker Activity
What do rabbit populations, spiral galaxies, flower petals, and programming interviews have in common? They all involve the famous Fibonacci sequence! This seemingly simple mathematical concept appears everywhere in nature and forms the foundation for understanding dynamic programming.
But here’s the fascinating part: while Fibonacci might seem like just an academic exercise, the patterns and techniques you learn from it apply to countless real-world problems. From calculating compound interest to optimizing resource allocation, linear DP is everywhere.
Lesson Overview
- Duration: 75 minutes
- Prerequisites: Basic DP concepts, memoization vs tabulation
- Materials Needed: Python development environment, calculator for verification
2. Learning Objectives and Session Outline (5 minutes)
What We’ll Cover Today:
- Fibonacci Deep Dive - Multiple approaches and optimizations
- Linear DP Patterns - Understanding one-dimensional state transitions
- Space Optimization Techniques - From O(n) to O(1) space complexity
- Problem Variations - Tribonacci, step counting, and more
- Real-World Applications - Where linear DP appears in practice
Success Criteria:
By the end of this session, you should be able to recognize linear DP patterns, implement efficient solutions, and apply space optimization techniques to any one-dimensional DP problem.
3. Foundation Knowledge (15-20 minutes)
Core Concepts
Understanding Linear Dynamic Programming
Linear DP refers to problems where the state depends only on a single parameter (usually an index or position), and each state transitions to a fixed number of previous states. The “linear” aspect comes from the one-dimensional nature of the state space.
Real-World Analogy: Think of climbing a staircase where you can take 1 or 2 steps at a time. To reach step n, you must have come from either step n-1 or step n-2. This dependency on previous states in a sequence is the essence of linear DP.
Why This Matters: Linear DP problems are:
- Often the simplest to understand and implement
- Great for learning DP fundamentals
- Common in technical interviews
- Building blocks for more complex DP patterns
The Fibonacci Sequence: A Perfect Starting Point
The Fibonacci sequence is defined as:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
This gives us: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Mathematical Properties:
- Golden Ratio Connection: F(n)/F(n-1) approaches φ = (1+√5)/2 ≈ 1.618
- Growth Rate: Fibonacci numbers grow exponentially
- Binet’s Formula: Closed-form expression for F(n)
Linear DP Characteristics
Problems that fit the linear DP pattern typically have:
- Single Parameter State: dp[i] represents the solution for position/size i
- Fixed Dependencies: Each state depends on a constant number of previous states
- Sequential Processing: We can compute states in order from base cases
- Space Optimization Potential: Often only need recent values, not entire history
Key Terminology
- Linear Recurrence: Recurrence relation where each term depends linearly on previous terms
- State Transition: How we move from one state to the next
- Rolling Array: Space optimization technique using circular buffer
- Closed-Form Solution: Mathematical formula that directly computes the result
- Matrix Exponentiation: Advanced technique for faster computation of linear recurrences
4. Detailed Explanation and Examples (25-30 minutes)
Fibonacci: Evolution from Naive to Optimal
Approach 1: Naive Recursion
def fibonacci_naive(n):
"""
Naive recursive approach - exponential time complexity
Time: O(2^n), Space: O(n) for recursion stack
"""
if n <= 1:
return n
return fibonacci_naive(n-1) + fibonacci_naive(n-2)
# Problem: Massive redundant computation
# For F(5): F(3) is computed 2 times, F(2) is computed 3 times, F(1) is computed 5 times
Why This is Inefficient: The recursive tree shows exponential growth in redundant calculations. For F(40), this approach makes over 1 billion function calls!
Approach 2: Memoization (Top-Down DP)
def fibonacci_memo(n, memo=None):
"""
Memoized recursive approach
Time: O(n), Space: O(n) for memo + O(n) for recursion stack
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
else:
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
# Using Python's built-in decorator
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_memo_decorator(n):
"""
Clean memoization using Python decorator
"""
if n <= 1:
return n
return fibonacci_memo_decorator(n-1) + fibonacci_memo_decorator(n-2)
Approach 3: Tabulation (Bottom-Up DP)
def fibonacci_tabulation(n):
"""
Bottom-up tabulation approach
Time: O(n), Space: O(n)
"""
if n <= 1:
return n
# Create table to store all values from 0 to n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Fill table bottom-up
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Approach 4: Space-Optimized Tabulation
def fibonacci_optimized(n):
"""
Space-optimized approach - only store what we need
Time: O(n), Space: O(1)
"""
if n <= 1:
return n
# Only need previous two values
prev2 = 0 # F(0)
prev1 = 1 # F(1)
for i in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
# Alternative with more descriptive names
def fibonacci_optimized_v2(n):
"""
Same algorithm with clearer variable names
"""
if n <= 1:
return n
fib_prev_prev = 0
fib_prev = 1
for i in range(2, n + 1):
fib_current = fib_prev + fib_prev_prev
fib_prev_prev = fib_prev
fib_prev = fib_current
return fib_prev
Advanced Techniques
Matrix Exponentiation for O(log n) Solution
def matrix_multiply(A, B):
"""
Multiply two 2x2 matrices
"""
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]
def matrix_power(matrix, n):
"""
Calculate matrix^n using fast exponentiation
Time: O(log n), Space: O(1)
"""
if n == 1:
return matrix
result = [[1, 0], [0, 1]] # Identity matrix
base = matrix
while n > 0:
if n % 2 == 1:
result = matrix_multiply(result, base)
base = matrix_multiply(base, base)
n //= 2
return result
def fibonacci_matrix(n):
"""
Fibonacci using matrix exponentiation
Based on: [F(n+1), F(n)] = [F(n), F(n-1)] * [[1,1],[1,0]]
"""
if n <= 1:
return n
base_matrix = [[1, 1], [1, 0]]
result_matrix = matrix_power(base_matrix, n)
return result_matrix[0][1] # This gives us F(n)
Linear DP Pattern Variations
Tribonacci Sequence
def tribonacci(n):
"""
Tribonacci: T(n) = T(n-1) + T(n-2) + T(n-3)
Base cases: T(0)=0, T(1)=1, T(2)=1
"""
if n == 0:
return 0
if n <= 2:
return 1
# Space-optimized approach
a, b, c = 0, 1, 1
for i in range(3, n + 1):
next_val = a + b + c
a, b, c = b, c, next_val
return c
Generalized Linear Recurrence
def solve_linear_recurrence(coefficients, initial_values, n):
"""
Solve general linear recurrence:
a(n) = c1*a(n-1) + c2*a(n-2) + ... + ck*a(n-k)
Args:
coefficients: [c1, c2, ..., ck]
initial_values: [a(0), a(1), ..., a(k-1)]
n: target index
"""
if n < len(initial_values):
return initial_values[n]
k = len(coefficients)
dp = initial_values[:]
for i in range(len(initial_values), n + 1):
next_val = sum(coefficients[j] * dp[i-1-j] for j in range(k))
dp.append(next_val)
return dp[n]
# Example: Fibonacci with this general solver
def fibonacci_general(n):
return solve_linear_recurrence([1, 1], [0, 1], n)
Real-World Linear DP Applications
Financial Calculations
def compound_interest_dp(principal, rate, years):
"""
Calculate compound interest using DP approach
amount[year] = amount[year-1] * (1 + rate)
"""
amounts = [0] * (years + 1)
amounts[0] = principal
for year in range(1, years + 1):
amounts[year] = amounts[year - 1] * (1 + rate)
return amounts[years]
def loan_payment_schedule(loan_amount, monthly_rate, months):
"""
Calculate remaining loan balance each month
"""
balances = [0] * (months + 1)
balances[0] = loan_amount
# Assuming fixed payment amount (calculated separately)
monthly_payment = calculate_monthly_payment(loan_amount, monthly_rate, months)
for month in range(1, months + 1):
interest = balances[month - 1] * monthly_rate
principal_payment = monthly_payment - interest
balances[month] = balances[month - 1] - principal_payment
return balances
def calculate_monthly_payment(principal, rate, months):
"""Calculate fixed monthly payment using formula"""
if rate == 0:
return principal / months
return principal * (rate * (1 + rate)**months) / ((1 + rate)**months - 1)
5. Live Coding Demonstration (20-25 minutes)
Example 1: Climbing Stairs Problem
def climbing_stairs_analysis():
"""
Problem: You're climbing a staircase with n steps.
You can climb either 1 or 2 steps at a time.
How many distinct ways can you climb to the top?
This is actually Fibonacci in disguise!
"""
def climb_stairs_naive(n):
"""
Naive recursive approach
Time: O(2^n), Space: O(n)
"""
if n <= 2:
return n
return climb_stairs_naive(n-1) + climb_stairs_naive(n-2)
def climb_stairs_optimized(n):
"""
Space-optimized DP solution
Time: O(n), Space: O(1)
Logic: To reach step n, you must come from step n-1 or n-2
ways[n] = ways[n-1] + ways[n-2]
"""
if n <= 2:
return n
prev2 = 1 # ways to reach step 1
prev1 = 2 # ways to reach step 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
# Demonstration with trace
def climb_stairs_with_trace(n):
"""Show the step-by-step calculation"""
print(f"Calculating ways to climb {n} stairs:")
if n <= 2:
print(f"Base case: {n} ways")
return n
ways = [0] * (n + 1)
ways[1] = 1
ways[2] = 2
print(f"ways[1] = {ways[1]} (base case)")
print(f"ways[2] = {ways[2]} (base case)")
for i in range(3, n + 1):
ways[i] = ways[i-1] + ways[i-2]
print(f"ways[{i}] = ways[{i-1}] + ways[{i-2}] = {ways[i-1]} + {ways[i-2]} = {ways[i]}")
return ways[n]
# Test the implementation
def test_climbing_stairs():
test_cases = [1, 2, 3, 4, 5, 8]
for n in test_cases:
result = climb_stairs_optimized(n)
print(f"Stairs {n}: {result} ways")
Example 2: House Robber Linear Version
def house_robber_linear():
"""
Problem: Rob houses in a line, can't rob adjacent houses
Find maximum money that can be robbed
This demonstrates linear DP with max optimization
"""
def rob_houses_analysis(houses):
"""
Analysis: At each house, decide to rob or not rob
If rob current: can't rob previous, so take dp[i-2] + houses[i]
If skip current: take dp[i-1]
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
"""
pass
def rob_tabulation(houses):
"""
Bottom-up DP solution
Time: O(n), Space: O(n)
"""
if not houses:
return 0
if len(houses) == 1:
return houses[0]
n = len(houses)
dp = [0] * n
dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
return dp[n-1]
def rob_optimized(houses):
"""
Space-optimized version
Time: O(n), Space: O(1)
"""
if not houses:
return 0
if len(houses) == 1:
return houses[0]
prev2 = houses[0] # dp[i-2]
prev1 = max(houses[0], houses[1]) # dp[i-1]
for i in range(2, len(houses)):
current = max(prev1, prev2 + houses[i])
prev2, prev1 = prev1, current
return prev1
def rob_with_trace(houses):
"""Show decision process"""
print(f"Houses: {houses}")
if len(houses) <= 1:
return houses[0] if houses else 0
dp = [0] * len(houses)
dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
print(f"dp[0] = {dp[0]} (rob house 0)")
print(f"dp[1] = max({houses[0]}, {houses[1]}) = {dp[1]}")
for i in range(2, len(houses)):
rob_current = dp[i-2] + houses[i]
skip_current = dp[i-1]
dp[i] = max(rob_current, skip_current)
action = "rob" if rob_current > skip_current else "skip"
print(f"dp[{i}] = max({skip_current}, {dp[i-2]}+{houses[i]}) = max({skip_current}, {rob_current}) = {dp[i]} ({action})")
return dp[-1]
# Test cases
test_houses = [
[2, 7, 9, 3, 1], # Expected: 12 (rob 0,2,4)
[1, 2, 3, 1], # Expected: 4 (rob 0,2)
[5, 1, 3, 9], # Expected: 14 (rob 0,3)
]
for houses in test_houses:
result = rob_with_trace(houses)
print(f"Maximum robbed: {result}\n")
Example 3: Cost Climbing Stairs
def cost_climbing_stairs():
"""
Problem: Given cost array, find minimum cost to reach top
You can start from step 0 or 1, and can climb 1 or 2 steps at a time
"""
def min_cost_climbing_stairs(cost):
"""
DP solution for minimum cost climbing
dp[i] = minimum cost to reach step i
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
"""
n = len(cost)
if n <= 1:
return 0
# dp[i] represents min cost to reach step i
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# Can start from step 0 or 1, so take min of last two
return min(dp[n-1], dp[n-2])
def min_cost_optimized(cost):
"""
Space-optimized version
Time: O(n), Space: O(1)
"""
n = len(cost)
if n <= 1:
return 0
prev2 = cost[0]
prev1 = cost[1]
for i in range(2, n):
current = cost[i] + min(prev1, prev2)
prev2, prev1 = prev1, current
return min(prev1, prev2)
# Test with trace
def min_cost_with_trace(cost):
"""Show the decision process"""
print(f"Cost array: {cost}")
n = len(cost)
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
print(f"dp[0] = {dp[0]} (cost to reach step 0)")
print(f"dp[1] = {dp[1]} (cost to reach step 1)")
for i in range(2, n):
from_prev1 = dp[i-1] + cost[i]
from_prev2 = dp[i-2] + cost[i]
dp[i] = min(from_prev1, from_prev2)
chosen = "step-1" if from_prev1 < from_prev2 else "step-2"
print(f"dp[{i}] = {cost[i]} + min(dp[{i-1}], dp[{i-2}]) = {cost[i]} + min({dp[i-1]}, {dp[i-2]}) = {dp[i]} (via {chosen})")
result = min(dp[n-1], dp[n-2])
print(f"Final: min(dp[{n-1}], dp[{n-2}]) = min({dp[n-1]}, {dp[n-2]}) = {result}")
return result
# Test cases
test_costs = [
[10, 15, 20], # Expected: 15
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1], # Expected: 6
]
for cost in test_costs:
result = min_cost_with_trace(cost)
print(f"Minimum cost: {result}\n")
6. Hands-On Practice (30-40 minutes)
Exercise 1: Basic Practice - N-th Tribonacci Number (10 minutes)
Objective: Implement the Tribonacci sequence using both memoization and space-optimized tabulation.
Problem: The Tribonacci sequence is defined as:
- T(0) = 0, T(1) = 1, T(2) = 1
- T(n) = T(n-1) + T(n-2) + T(n-3) for n > 2
Instructions:
- Implement using memoization
- Implement using space-optimized tabulation
- Compare performance and space usage
Starter Code:
def tribonacci_memo(n, memo=None):
"""
Tribonacci using memoization
Time: O(n), Space: O(n)
"""
# Your implementation here
pass
def tribonacci_optimized(n):
"""
Space-optimized tribonacci
Time: O(n), Space: O(1)
"""
# Your implementation here
pass
# Test cases
test_cases = [0, 1, 2, 4, 7, 25]
for n in test_cases:
memo_result = tribonacci_memo(n)
opt_result = tribonacci_optimized(n)
print(f"T({n}) = {memo_result} (memo), {opt_result} (optimized)")
Solution:
def tribonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n == 0:
return 0
if n <= 2:
return 1
memo[n] = (tribonacci_memo(n-1, memo) +
tribonacci_memo(n-2, memo) +
tribonacci_memo(n-3, memo))
return memo[n]
def tribonacci_optimized(n):
if n == 0:
return 0
if n <= 2:
return 1
a, b, c = 0, 1, 1
for i in range(3, n + 1):
next_val = a + b + c
a, b, c = b, c, next_val
return c
Exercise 2: Intermediate Challenge - Delete and Earn (15 minutes)
Objective: Apply linear DP to a more complex optimization problem.
Problem: Given an array of integers, you can delete any element and earn points equal to that element’s value. When you delete an element, all elements equal to that value are also deleted, and you cannot delete elements with values that differ by exactly 1 from the deleted element.
Example:
- Input: [3, 4, 2]
- Output: 6 (delete 2 and 4, earn 2+4=6 points)
Requirements:
- Transform the problem into a linear DP problem
- Implement space-optimized solution
- Handle edge cases
Hints:
- Think about grouping elements by value
- This becomes similar to house robber once transformed
Exercise 3: Creative Application - Decode Ways (15 minutes)
Objective: Apply linear DP to a string decoding problem.
Challenge: A message containing letters from A-Z is encoded as numbers where ‘A’=1, ‘B’=2, …, ‘Z’=26. Given an encoded string, count the number of ways to decode it.
Example:
- Input: “226”
- Output: 3 (interpretations: “2,2,6”→“BBF”, “22,6”→“VF”, “2,26”→“BZ”)
Extension Ideas:
- Handle strings with leading zeros
- Return actual decoded strings, not just count
- Handle invalid encodings gracefully
7. Common Pitfalls and Troubleshooting (10 minutes)
Frequent Mistakes
-
Problem: Off-by-one errors in indexing Cause: Confusing 0-based vs 1-based indexing Solution: Always trace through small examples manually
-
Problem: Incorrect base case initialization Cause: Not handling edge cases properly (n=0, n=1) Solution: Test with minimal inputs first
-
Problem: Space optimization bugs Cause: Incorrect variable updates in rolling arrays Solution: Be careful with assignment order:
prev2, prev1 = prev1, current -
Problem: Integer overflow for large Fibonacci numbers Cause: Fibonacci grows exponentially Solution: Use modular arithmetic or arbitrary precision integers
Debugging Strategies
def debug_linear_dp():
"""
Common debugging techniques for linear DP
"""
def trace_fibonacci(n):
"""Add tracing to see computation flow"""
print(f"Computing F({n})")
if n <= 1:
print(f"Base case: F({n}) = {n}")
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
print(f"F({i}) = F({i-1}) + F({i-2}) = {dp[i-1]} + {dp[i-2]} = {dp[i]}")
return dp[n]
def validate_space_optimization(n):
"""Compare normal vs space-optimized versions"""
# Normal version
normal_result = fibonacci_tabulation(n)
# Space-optimized version
opt_result = fibonacci_optimized(n)
assert normal_result == opt_result, f"Mismatch: {normal_result} vs {opt_result}"
print(f"✓ Both versions give F({n}) = {normal_result}")
# Test range
for i in range(10):
validate_space_optimization(i)
Performance Optimization Tips
def performance_comparison():
"""
Compare different approaches for large n
"""
import time
def time_function(func, n, *args):
start = time.time()
result = func(n, *args)
end = time.time()
return result, end - start
n = 35 # Large enough to see differences
# Test different approaches
approaches = [
("Memoization", fibonacci_memo),
("Tabulation", fibonacci_tabulation),
("Optimized", fibonacci_optimized),
("Matrix", fibonacci_matrix)
]
for name, func in approaches:
try:
result, time_taken = time_function(func, n)
print(f"{name}: F({n}) = {result}, Time: {time_taken:.6f}s")
except Exception as e:
print(f"{name}: Error - {e}")
8. Best Practices and Professional Tips (5 minutes)
Industry Standards
def professional_linear_dp_template():
"""
Professional template for linear DP problems
"""
def solve_linear_dp_problem(input_data):
"""
Template for solving linear DP problems
Args:
input_data: Problem-specific input
Returns:
Optimal solution value
Time Complexity: O(n)
Space Complexity: O(1) after optimization
"""
# Step 1: Handle edge cases
if not input_data:
return 0
n = len(input_data)
if n == 1:
return input_data[0] # Problem-specific base case
# Step 2: Initialize for space-optimized solution
prev2 = 0 # dp[i-2]
prev1 = 0 # dp[i-1]
# Step 3: Process each state
for i in range(n):
# Problem-specific recurrence relation
current = max(prev1, prev2 + input_data[i]) # Example
prev2, prev1 = prev1, current
return prev1
Code Organization Tips
class LinearDPSolver:
"""
Class-based approach for related linear DP problems
"""
def __init__(self):
self.memo = {}
def fibonacci(self, n):
"""Standard Fibonacci implementation"""
return self._linear_recurrence(n, [1, 1], [0, 1])
def tribonacci(self, n):
"""Tribonacci using same framework"""
return self._linear_recurrence(n, [1, 1, 1], [0, 1, 1])
def _linear_recurrence(self, n, coefficients, initial_values):
"""Generic linear recurrence solver"""
if n < len(initial_values):
return initial_values[n]
# Space-optimized implementation
values = initial_values[:]
for i in range(len(initial_values), n + 1):
next_val = sum(coefficients[j] * values[-1-j]
for j in range(len(coefficients)))
values.append(next_val)
# Keep only necessary values for space optimization
if len(values) > len(coefficients):
values.pop(0)
return values[-1]
Performance Considerations
- Space Optimization: Always try to reduce from O(n) to O(1) space
- Integer Overflow: Use modular arithmetic for very large numbers
- Early Termination: Some problems allow early exit conditions
- Preprocessing: Sometimes transforming input simplifies the DP
Next Steps in Your Learning Journey
- Master 2D DP: Move to problems with two-dimensional state spaces
- Study More Patterns: Learn about interval DP, digit DP, and bitmask DP
- Practice Variations: Solve problems that modify classic linear DP patterns
- Interview Preparation: Practice explaining your approach clearly and concisely
9. Summary and Review (5 minutes)
Key Takeaways
- Linear DP Foundation: Single parameter state with fixed dependencies on previous states
- Space Optimization: Most linear DP problems can be optimized from O(n) to O(1) space
- Pattern Recognition: Many problems reduce to variations of Fibonacci or house robber patterns
- Implementation Choices: Memoization for complex recursion, tabulation for sequential processing
Quick Review Questions
- What’s the space complexity of the naive recursive Fibonacci approach?
- How do you optimize linear DP space complexity from O(n) to O(1)?
- What’s the key insight that makes the climbing stairs problem equivalent to Fibonacci?
Answers:
- O(n) due to recursion stack depth, despite exponential time complexity
- Keep only the necessary previous values needed for the recurrence relation
- To reach step n, you must come from step n-1 or n-2, giving the same recurrence as Fibonacci
For Instructors
Teaching Tips
- Start Simple: Begin with standard Fibonacci before introducing variations
- Emphasize Space Optimization: Show how to systematically reduce space complexity
- Use Visual Aids: Draw arrays and show how values are computed step by step
- Practice Pattern Recognition: Help students see the underlying patterns in different problems
Assessment Ideas
- Implementation Comparison: Have students implement same problem with different approaches
- Space Optimization Exercise: Give O(n) solution, ask students to optimize to O(1)
- Pattern Recognition Quiz: Present new problems, ask students to identify the linear DP pattern
Adaptation Notes
- Beginners: Focus on understanding the basic pattern before optimization
- Advanced Students: Challenge with matrix exponentiation and closed-form solutions
- Time Constraints: Can skip advanced techniques and focus on core optimization patterns