1 import java.util.*;
 2 
 3 public class Solution {
 4     public int climbStairs(int n) {
 5         Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
 6         table.put(2, 2);
 7         table.put(1, 1);
 8         table.put(0, 0);
 9         if (n < 0) return 0;
10         return climb(n, table);
11     }
12     
13     public int climb(int n, Hashtable<Integer, Integer> table) {
14         if (table.containsKey(n)) return table.get(n);
15         else {
16             table.put(n, climb(n-1, table) + climb(n-2, table));
17             return table.get(n);
18         }
19     }
20 }