leetcode

commit 17aabb25ba1a5be13448189c828e6741748b99c3
parent 54ba5d4a4aa53aff67359c8382ee8685ad12d165
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 21 Jan 2023 15:22:34 +0100

Dynamic Programming I: Day 1

Diffstat:
M
Problems/0509.cpp
 | 
16
++++++++++++++++
M
Problems/1137.cpp
 | 
18
++++++++++++++++++

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/0509.cpp b/Problems/0509.cpp
@@ -1,3 +1,4 @@
+// memorization approach
 class Solution {
 public:
   int fib(int n) {
@@ -8,3 +9,18 @@ public:
     return f[n];
   }
 };
+
+// optimized, memorize only the previous two values
+class Solution {
+public:
+  int fib(int n) {
+    if (n == 0) return 0;
+    int a = 0, b = 1;
+    for (int i = 2; i <= n; i++) {
+      int tmp = a + b;
+      a = b;
+      b = tmp;
+    }
+    return b;
+  }
+};
diff --git a/Problems/1137.cpp b/Problems/1137.cpp
@@ -1,3 +1,4 @@
+// memorization approach
 class Solution {
 public:
   int tribonacci(int n) {
@@ -9,3 +10,20 @@ public:
     return f[n];
   }
 };
+
+// optimized, memorize only the previous three values
+class Solution {
+public:
+  int tribonacci(int n) {
+    if (n == 0) return 0;
+    if (n == 1) return 1;
+    int a = 0, b = 1, c = 1;
+    for (int i = 3; i <= n; i++) {
+      int tmp = a + b + c;
+      a = b;
+      b = c;
+      c = tmp;
+    }
+    return c;
+  }
+};