790

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))
+}