Re: [閒聊] 每日leetcode
昨天的
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1767540510.A.4D3.html
推
01/04 23:31,
3天前
, 1F
01/04 23:31, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1560 之 1561 篇)：