Part IV · Fundamental Algorithm Design Paradigms
23. Dynamic Programming: The Core Method
8 lessons•40 topics•Intermediate
8 of 8 lessons published
23.015 animated
Recognizing DP
- Overlapping subproblems
- Optimal substructure
- DAG interpretation
- State design
- Transition function
23.027 animated
DP workflow
- Define state
- Define transition
- Base cases
- Evaluation order
- Answer extraction
- Complexity
- Space optimization
23.035 animated
Top-down memoization
- Recursive memo
- Sentinel values
- Cache invalid states
- Stack depth
- Memoization vs pure recursion
23.044 animated
Bottom-up tabulation
- Iterative dependency order
- Forward vs backward transitions
- Boundary handling
- Table construction
23.056 animated
Canonical beginner DP
- Climbing stairs
- Fibonacci
- House robber
- Min cost climbing stairs
- Decode ways
- Coin change
23.064 animated
DP optimization basics
- Rolling arrays
- One-row compression
- State elimination
- Reverse iteration for 0/1 choice
23.075 animated
Reconstructing solutions
- Parent pointers
- Choice tables
- Traceback
- Counting vs optimizing
- Multiple optimal solutions
23.081 animated
DP correctness
- State completeness
- Dependency acyclicity
- Induction on state order
- Transition exhaustiveness