Broken Profile DP (Plug DP)
Grid tiling with dominoes. Process row by row, using a bitmask for the boundary between rows.
Lessons
1. Intro
Grid tiling with profiles
2. The Profile Concept
Column boundary states
3. Quiz: Profile Concept
Understanding the boundary
4. Why Bitmasks Work
Compact state
5. Bitmask Encoding - Walkthrough
How to represent states
6. State Transitions
Column to column
7. State Transitions - Walkthrough
How masks change
8. Quiz: Profile Encoding
Knowledge check
9. Counting Tilings - Problem Statement
CSES 2181
10. Counting Tilings - State Definition
What DP tracks
11. Counting Tilings - Filling a Column
Recursive placement
12. Counting Tilings - Transition Formula
Combining paths
13. Counting Tilings - Implementation
Full solution
14. Counting Tilings - Walkthrough
Tracing the classic problem
15. Challenge: Transition Enumeration
Generating valid transitions
16. Quiz: Transition Count
Knowledge check
17. Tri Tiling - Problem Statement
UVa 10918
18. Tri Tiling - Small Cases
Manual enumeration
19. Tri Tiling - Recurrence Discovery
Pattern from profiles
20. Tri Tiling - Implementation
Recurrence solution
21. Tri Tiling - Walkthrough
Non-standard grid
22. When Width Is Fixed
Recurrence vs DP
23. Quiz: Why Small Width
Complexity considerations
24. LeetCode 790 Domino and Tromino Tiling - Problem Statement
LeetCode 790
25. Domino and Tromino - Profile States
Three profile types
26. Domino and Tromino - Transitions
Tile placement choices
27. Domino and Tromino - Simplified Recurrence
Final formula
28. Simplified Recurrence - Walkthrough
Finding the pattern
29. Domino and Tromino - Implementation
DP or recurrence
30. Domino and Tromino - Walkthrough
Mixed tile shapes
31. Quiz: Profile Count
Knowledge check
32. Chessboard Coloring - Problem Statement
Non-tiling variant
33. Hamiltonian Paths - Problem Statement
Path DP variant
34. Challenge: Larger Tiles
Beyond dominoes
35. When to Use Broken Profile DP
Problem recognition
36. Pattern - Broken Profile Recognition
When to apply this technique
37. Course Conclusion
You've completed the DP course
38. Complexity Analysis
Time and space
39. Complexity Analysis - Walkthrough
Understanding the bounds
40. Common Mistakes
Pitfalls to avoid
41. Common Mistakes - Walkthrough
Debugging tips
42. Section Recap
What we learned
Practice Problems
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Classic domino tiling with broken profile. Foundation for all plug DP problems.
Profile DP on bracket sequence. State encodes coloring of visible bracket pairs.
Bitmask DP on grid rows. Simpler broken profile before full plug DP complexity.
Bracket sequence with profile state. Counting valid configurations column by column.
Chess piece placement with broken profile. Tests understanding of diagonal state encoding.
Introduction to tiling DP. Simpler profile before full broken profile complexity.
Rectangle tiling with backtracking/DP. Tests profile state enumeration skills.
Two-path grid DP. Related state-space thinking to broken profile approaches.
Two robots grid DP. Column-by-column processing similar to profile DP paradigm.