add lucas dynamic programming

realDuYuanChao · realDuYuanChao · commit 61afbc480473 · 2020-10-26T10:12:57.000+08:00
diff --git a/src/main/java/com/examplehub/dynamicprogramming/LucasDP.java b/src/main/java/com/examplehub/dynamicprogramming/LucasDP.java
@@ -0,0 +1,24 @@
+package com.examplehub.dynamicprogramming;
+
+/** https://en.wikipedia.org/wiki/Lucas_number */
+public class LucasDP {
+
+  /**
+   * Return nth lucas number using dynamic programming.
+   *
+   * @param n the nth.
+   * @return the nth number of lucas series.
+   */
+  public static int lucas(int n) {
+    if (n == 0) {
+      return 2;
+    }
+    int[] lucasNumbers = new int[n + 1];
+    lucasNumbers[0] = 2;
+    lucasNumbers[1] = 1;
+    for (int i = 2; i <= n; i++) {
+      lucasNumbers[i] = lucasNumbers[i - 1] + lucasNumbers[i - 2];
+    }
+    return lucasNumbers[n];
+  }
+}
diff --git a/src/test/java/com/examplehub/dynamicprogramming/LucasDPTest.java b/src/test/java/com/examplehub/dynamicprogramming/LucasDPTest.java
@@ -0,0 +1,15 @@
+package com.examplehub.dynamicprogramming;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class LucasDPTest {
+  @Test
+  void test() {
+    int[] lucasNumbers = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123};
+    for (int i = 0; i < lucasNumbers.length; i++) {
+      assertEquals(lucasNumbers[i], LucasDP.lucas(i));
+    }
+  }
+}
