javac DynamicProgrammingPatterns.java && ./run --mode=interview-prep
Dynamic Programming Patterns
Master dynamic programming with visual state transitions. See how overlapping subproblems are solved, recurrences are built, and states are optimized toward the solution — one step at a time.
01_fibonacci.java
Fibonacci is the classic DP starter: each value depends on previous values. Instead of recomputing work, we store the answer for each state and reuse it.
General Definition
A recurrence where the answer for a larger state is built from the answers of smaller states, and the subproblems overlap.
Professional Definition — say this in an interview
Fibonacci DP works by defining dp[i] = dp[i-1] + dp[i-2] and filling the table from left to right. This reduces exponential repeated work to O(n) time and O(n) space, which is the canonical introduction to dynamic programming.
Interview keywords — if you hear these, think of this pattern
overlapping subproblemstop-down/bottom-upstate transitionfib sequencememoization
SOURCE
Java
public int fib(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }
DEBUGGER — live watch0 / 8
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
Not started
DEBUG STEPS0
Press ▶ Play or Next to start stepping through the algorithm.
Practice these — same pattern, different skin