Multi-Dimensional DP
When one dimension is not enough. You'll design DP states with multiple parameters for grids and strings.
Lessons
1. Intro
Why multi-dimensional DP
2. Why One Dimension Fails
The limitation
3. What Is Multi-Dimensional DP?
Core concept
4. Vocabulary - 2D State
Two parameters
5. The Same Four Steps
Pattern reminder
6. Quiz: When to Add Dimensions
Knowledge check
7. Codeforces 478D Red Green Towers - Problem Statement
Codeforces 478D
8. Codeforces 478D Red Green Towers - The Setup
Understanding constraints
9. Codeforces 478D Red Green Towers - Finding the Height
First observation
10. Codeforces 478D Red Green Towers - State Definition
Two parameters
11. Codeforces 478D Red Green Towers - Transition
Color choice
12. Codeforces 478D Red Green Towers - Base Cases
Starting point
13. Codeforces 478D Red Green Towers - Final Answer
Valid configurations
14. Codeforces 478D Red Green Towers - Implementation
The code
15. Lessons from Red Green Towers
summary
16. Grid 1 - Problem Statement
AtCoder DP-H
17. Grid 1 - Understanding the Grid
The setup
18. Grid 1 - State Definition
What dp[i][j] means
19. Grid 1 - Transition
Coming from above or left
20. Grid 1 - Handling Walls
Blocked cells
21. Grid 1 - Base Cases
Starting point
22. Grid 1 - Implementation
The code
23. Lessons from Grid 1
summary
24. Edit Distance - Problem Statement
CSES 1639
25. Edit Distance - The Three Operations
Insert, delete, replace
26. Edit Distance - State Definition
Prefix to prefix
27. Edit Distance - Transition
Match or operate
28. Edit Distance - Base Cases
Empty strings
29. Edit Distance - Implementation
The code
30. Lessons from Edit Distance
summary
31. Grid Paths - Problem Statement
Counting paths in a grid
32. Grid Paths - The Setup
Understanding the grid
33. Grid Paths - State Definition
What dp[i][j] means
34. Grid Paths - Transition
From above or left
35. Grid Paths - Implementation
Complete solution
36. LeetCode 64 Minimum Path Sum - Problem Statement
Find cheapest path
37. LeetCode 64 Minimum Path Sum - State Definition
Minimum cost to cell
38. LeetCode 64 Minimum Path Sum - Transition
Choose cheaper path
39. LeetCode 64 Minimum Path Sum - Implementation
Complete solution
40. Section Recap
What we learned
Practice Problems
Classic 3D DP with count constraints - perfect for multi-dimensional state practice
Grid path counting with obstacles - teaches handling constraints in 2D DP
2D DP tracking two string indices simultaneously - teaches merging sequences
Grid path counting with large dimensions - teaches inclusion-exclusion with DP.
Two-path grid DP where paths must cross - teaches multi-agent state design
Grid DP where dp[i][j] is side length of largest square - builds from subproblems in 2D
More DP dimensions, multi-variable transitions.
Foundational 2D grid path counting with obstacles - the classic grid DP template.
Classic Levenshtein distance with insert/delete/replace operations.
Good classic problem
Shows how to compress a 2D grid into O(n) space with bottom-up sweeps