昨天的
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
}

大師