diff options
| -rw-r--r-- | 790/go.mod | 3 | ||||
| -rw-r--r-- | 790/main.go | 33 |
2 files changed, 36 insertions, 0 deletions
diff --git a/790/go.mod b/790/go.mod new file mode 100644 index 0000000..bf4d8d3 --- /dev/null +++ b/790/go.mod @@ -0,0 +1,3 @@ +module 790 + +go 1.19 diff --git a/790/main.go b/790/main.go new file mode 100644 index 0000000..3fe5b3c --- /dev/null +++ b/790/main.go @@ -0,0 +1,33 @@ +package main + +import "fmt" + +func countFib(n int64) int64 { + f := make([]int64, n+1) + + f[0] = 0 + f[1] = 1 + f[2] = 2 + f[3] = 5 + + for i := int64(4); i <= n; i++ { + f[i] = (2*f[i-1] + f[i-3]) % 1000000007 + } + + return f[n] +} + +func numTilings(n int) int { + + if n <= 2 { + return n + } + + return int(countFib(int64(n))) +} + +func main() { + // fmt.Println(numTilings(10)) + // fmt.Println(numTilings(1)) + fmt.Println(numTilings(2)) +} |