The Painting a Grid With Three Different Colors problem asks you to count ways to color an m×n grid with 3 colors such that no two adjacent cells (horizontally or vertically) share the same color. This hard DP uses row-pattern precomputation and column-by-column transitions. The dynamic programming interview pattern is demonstrated through column-profile DP.
Microsoft, Meta, Amazon, Google, and Bloomberg ask this hard DP problem because with m up to ~5 (small), enumerating valid column patterns and precomputing compatible column pairs gives an efficient O(n * V²) solution where V is the number of valid column patterns. This tests DP with precomputed state transitions.
Column profile DP. Generate all valid column colorings (no two adjacent cells same color): 3 * 2^(m-1) at most. For each pair of valid columns, check compatibility (no same color horizontally adjacent). dp[j][pattern] = ways to color first j columns where column j has pattern. Transition: dp[j+1][p'] = sum of dp[j][p] for all p compatible with p'. Answer = sum of dp[n].
m=2, n=1. Valid patterns: 6 (pairs ab where a≠b with 3 colors: 32=6). Any single column is valid. Answer = 6. m=1, n=3. Single row 3 cells: 32*2=12 valid colorings. m=2, n=3. More complex transitions between column pairs. Answer = 54 (standard result).
Grid coloring problems with small m use column profile DP. Steps: (1) enumerate valid column patterns, (2) build compatibility graph between column patterns, (3) DP over columns using the graph. The number of valid patterns is at most 3*2^(m-1), manageable for m≤5. This technique generalizes to "tile an m×n grid with colored dominos" and similar problems.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| K Inverse Pairs Array | Hard | Solve | |
| Race Car | Hard | Solve | |
| Non-negative Integers without Consecutive Ones | Hard | Solve | |
| Student Attendance Record II | Hard | Solve | |
| Count Ways to Distribute Candies | Hard | Solve |
