From 1a8bad09d6e7a380587d1334ead783dde6757d5f Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Sat, 24 Dec 2022 16:24:58 +0330 Subject: 790 --- 790/go.mod | 3 +++ 790/main.go | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+) create mode 100644 790/go.mod create mode 100644 790/main.go 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)) +} -- cgit v1.2.3