Add dynamic programming code

jbee37142 · jbee37142 · commit d79b0a5fc2e0 · 2017-05-29T21:03:15.000+09:00
diff --git a/src/test/java/algorithm/dp/FiboByDp.java b/src/test/java/algorithm/dp/FiboByDp.java
@@ -0,0 +1,33 @@
+package algorithm.dp;
+
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
+public class FiboByDp {
+    @Test
+    public void test() {
+        assertThat(5, is(fiboByDp(5)));
+        assertThat(8, is(fiboByDp(6)));
+        assertThat(13, is(fiboByDp(7)));
+    }
+
+    public int fiboByDp(int num) {
+        return calcFibo(num, new int[num + 1]);
+    }
+
+    private int calcFibo(int num, int[] cache) {
+        if (num < 2) {
+            return num;
+        }
+
+        //in java, int[] is initialized by 0.
+        if (cache[num] != 0) {
+            return cache[num];
+        }
+
+        cache[num] = calcFibo(num - 1, cache) + calcFibo(num - 2, cache);
+        return cache[num];
+    }
+}
