# High Level Algorithm

1. n < 0: return 0, we went too far
2. n == 0: return 1, we reached the nth step.
1. N > 0: try taking 1 step and 2 step
1. Solve the problem using a Brute force recursive solution
2. Create an array to store each state you encounter and cache your calculation in the recursive case.
3. Add another base case where you reuse the cache value if you have seen the state.

# Implementation

`class Solution {    public int climbStairs(int n) {        return helper(n);    }       private int helper(int n) {        if (n == 0) {            // base case where we arrived at an answer            return 1;        } else if (n < 0) {            // base case where we went too far            return 0;         } else {            // recursive case where we try taking 1 step            // and 2 steps, adding the unique permuation            // of steps back            return helper(n-1) + helper(n-2);        }    }}`
`class Solution {    private int[] memo;    public int climbStairs(int n) {        // instantiate the datastructure to cache the calculation        // to each of our subproblems. i.e. what step we are on        memo = new int[n+1];        return helper(n);    }       private int helper(int n) {        if (n < 0) {            return 0;        } else if (memo[n] != 0) {            // If we stored something in our cache reuse it and avoid            // recalculating everything            return memo[n];        } else if (n == 0) {            return 1;        } else {            // store our calculation inside our cache so we don't            // have to recalculate it again for memo[n]            memo[n] = helper(n-1) + helper(n-2);            return memo[n];        }    }}`

--

--