hardDynamic Programming 1DPure DSA~25 min
Ways to Paint an N x 3 Grid
A status board has n rows of three cells. Each cell is painted one of three colors, and no two adjacent cells (horizontally or vertically) may share a color. Count the distinct valid colorings.
Problem
Given n, count the number of ways to paint an n x 3 grid using 3 colors such that no two adjacent cells (sharing an edge) have the same color. Return the count modulo 1e9 + 7.
Input
An integer n (number of rows).
Output
An integer: the number of valid colorings modulo 1e9 + 7.
Constraints
- 1 <= n <= 5000
Examples
Example 1
Input
n = 1
Output
12
A single row has 12 valid three-cell colorings.
Example 2
Input
n = 2
Output
54
Two rows yield 54 valid colorings.