Paint grid with color constraints
You must paint every cell of a grid that has 3 columns and n rows. Each cell is painted one of three colors (red, yellow, green). No two adjacent cells in the same row may share a color, and no two vertically adjacent cells (same column, consecutive rows) may share a color. Return the number of ways to paint the whole grid, modulo 1000000007. n is between 1 and 5000.
Implement
num_ways_paint(n: int) → intExamples
in
[1]out12What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[1]12not run yetsample