楼主:
JKWP (神楽めあ的烟灰缸)
2026-01-04 23:28:28昨天的
1411. Number of Ways to Paint N × 3 Grid
观察n=1, 可以发现总共有12种组合
然后这12种组合又可以分成2种形式
1. ABA : 绿红绿、红绿红...这种
2. ABC : 绿红黄、黄绿红...这种
这两种形式都出现6次
假设这一行是红绿黄,
那它的上一行可以是 : 绿红绿、绿黄绿、黄红绿、绿黄红
如果是红绿红
那可以是 : 黄红黄、绿红绿、绿黄绿、黄红绿、绿红黄
也就是说
1. ABA可以从3种ABA、2种ABC来
2. ABC可以从2种ABA、2种ABC来
找到规律就直接DP就好
golang code :
func numOfWays(n int) int {
mod := 1_000_000_007
prevABA, prevABC := 6, 6
curABA, curABC := 0, 0
for i := 1; i < n; i++ {
curABA = (prevABA*3 + prevABC*2) % mod
curABC = (prevABA*2 + prevABC*2) % mod
prevABA, prevABC = curABA, curABC
curABA, curABC = 0, 0
}
return (prevABA + prevABC) % mod
}