Runtime: 1 ms, faster than 10.33% of Java online submissions for Climbing Stairs. Memory Usage: 40.6 MB, less than 62.22% of Java online submissions for Climbing Stairs.
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
return climbStairsAux(n, 0, 0);
}
public int climbStairsAux(int n, int from, int step) {
if(map.containsKey(from+step))
return map.get(from+step);
if(from + step > n)
return 0;
if(from + step == n)
return 1;
int result = 0;
result = result + climbStairsAux(n, from + step, 1);
result = result + climbStairsAux(n, from + step, 2);
map.put(from + step, result);
return result;
}
}
or,
class Solution {
int total = 0;
Map<Integer, Integer> set = new HashMap<>();
public int climbStairs(int n) {
return climbStairsRec(n - 1) + climbStairsRec(n - 2);
}
public int climbStairsRec(int n) {
if(set.containsKey(n))
return set.get(n);
if(n == 0)
return 1;
if(n < 0)
return 0;
int intTotal = climbStairsRec(n - 1) + climbStairsRec(n - 2);
set.put(n, intTotal);
return intTotal;
}
}