Dynamic ProgrammingBeginner
Fibonacci Pattern
Each state depends on a fixed number of previous states, like Fibonacci numbers.
Problem: Climbing Stairs (n = 5)
You can climb 1 or 2 steps at a time. How many distinct ways can you climb to step 5?
1
1
_
_
_
_
Initialize base cases
dp[0] = 1 (one way to stay at ground), dp[1] = 1 (one way to reach step 1). Unknown values shown as '_'.
Step 1/6
Speed:
When to Use
- Climbing stairs
- House robber
- Decode ways
- State depends on previous 2-3 states
Key Indicators
- dp[i] depends on dp[i-1] and dp[i-2]
- Count ways to reach state
- Linear sequence of decisions
Complexity
Time
O(n)
Space
O(1) with space optimization
Common Problems
Climbing StairsHouse RobberDecode WaysFibonacci Number
Code
prev2, prev1 = base_case_0, base_case_1
for i in range(2, n+1):
current = prev1 + prev2 # or max/min
prev2, prev1 = prev1, currentWant all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)