24 lines
525 B
Go
24 lines
525 B
Go
package q790
|
|
|
|
const (
|
|
TopHalf int8 = iota
|
|
BottomHalf
|
|
Full
|
|
|
|
Modulo int = 1e9 + 7
|
|
)
|
|
|
|
func numTilings(n int) int {
|
|
cache := make([][3]int, n+1)
|
|
cache[0][Full] = 1
|
|
cache[1][Full] = 1
|
|
|
|
for w := 2; w <= n; w++ {
|
|
cache[w][Full] = (cache[w-1][Full] + cache[w-2][Full] + cache[w-1][TopHalf] + cache[w-1][BottomHalf]) % Modulo
|
|
cache[w][TopHalf] = (cache[w-1][BottomHalf] + cache[w-2][Full]) % Modulo
|
|
cache[w][BottomHalf] = (cache[w-1][TopHalf] + cache[w-2][Full]) % Modulo
|
|
}
|
|
return cache[n][Full]
|
|
}
|
|
|
|
var _ = numTilings
|