1. class Solution {
  2.     // To reach step n, you must have:
  3.     // Come from n-1 (1 step jump)
  4.     // Or from n-2 (2 step jump)
  5.     public int climbStairs(int n) {
  6.         if(n == 1)
  7.             return 1;
  8.  
  9.         int[] t = new int[n+1];
  10.         t[1] = 1;
  11.         t[2] = 2;
  12.         Arrays.fill(t, -1);
  13.  
  14.         return findSteps(n, t);
  15.     }
  16.  
  17.     public int findSteps(int n, int[] t)
  18.     {
  19.         if(n <= 2)
  20.             return n;
  21.  
  22.         if(t[n] != -1)
  23.             return t[n];
  24.  
  25.         t[n] = findSteps(n-1, t) + findSteps(n-2, t);
  26.         return t[n];
  27.     }
  28. }