[LeeCode][动态规划][简单]上楼梯

class Solution {
    /** 
        递归处理: 由于上楼梯的方式只有两种， 即一次一个台阶 或者 一次两个台阶
        假如 一次一个台阶, 剩下 n - 1 台阶  也就是求 f(n - 1)
        假如 一次两个台阶，剩下 n - 2 台阶  也就是求 f(n - 2）
        那么综合两种可能， 求 n 阶台阶可能性f(n) 就是求 f(n - 1) + f(n - 2) 
     */
    Map<Integer, Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        // 缓存结果
        if (map.containsKey(n)) {
            return map.get(n);
        } else {
            int nSolution = climbStairs(n-1)+climbStairs(n -2);
            map.put(n, nSolution);
            return nSolution;
        }
    }
}