add fibonacci dynamic programming

realDuYuanChao · realDuYuanChao · commit ba8d070fdd53 · 2020-10-09T10:12:38.000+08:00
diff --git a/src/main/java/com/examplehub/dynamicprogramming/FibonacciDP.java b/src/main/java/com/examplehub/dynamicprogramming/FibonacciDP.java
@@ -0,0 +1,20 @@
+package com.examplehub.dynamicprogramming;
+
+public class FibonacciDP {
+
+    /**
+     * Get nth fibonacci number.
+     *
+     * @param nth the nth
+     * @return nth fibonacci number.
+     */
+    public static int fibonacci(int nth) {
+        int[] fib = new int[nth + 2]; /* allocate 1 extra space to handle fibonacci[0] */
+        fib[0] = 0;
+        fib[1] = 1;
+        for (int i = 2; i <= nth; i++) {
+            fib[i] = fib[i - 1] + fib[i - 2];
+        }
+        return fib[nth];
+    }
+}
diff --git a/src/test/java/com/examplehub/dynamicprogramming/FibonacciDPTest.java b/src/test/java/com/examplehub/dynamicprogramming/FibonacciDPTest.java
@@ -0,0 +1,15 @@
+package com.examplehub.dynamicprogramming;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class FibonacciDPTest {
+    @Test
+    void testFibonacci() {
+        assertEquals(0, FibonacciDP.fibonacci(0));
+        assertEquals(1, FibonacciDP.fibonacci(1));
+        assertEquals(1, FibonacciDP.fibonacci(2));
+        assertEquals(34, FibonacciDP.fibonacci(9));
+    }
+}
