solve 70

1 files changed, 15 insertions, 0 deletions

diff --git a/c/0070/main.c b/c/0070/main.c
new file mode 100644
index 0000000..143eeb3
--- /dev/null
+++ b/c/0070/main.c
@@ -0,0 +1,15 @@
+#include <stdlib.h>
+
+int climbStairsImpl(int n, int* cache) {
+    if (n == 0) return 1;
+    if (n < 0) return 0;
+    if (cache[n] > 0) return cache[n];
+    int ret = climbStairsImpl(n-1, cache) + climbStairsImpl(n-2, cache);
+    cache[n] = ret;
+    return ret;
+}
+
+int climbStairs(int n) {
+    int *cache = malloc(sizeof(int) * (n+1));
+    return climbStairsImpl(n, cache);
+}