[数据结构与算法]爬楼梯（LeetCode）

题目：

爬楼梯，假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

思路：

爬1阶台楼梯有一种方法，爬2阶楼梯有两种方法，爬3阶楼梯有（1,1,1）（1,2）（2,1）有三种方法。。。往后依次类推，你会发现爬n阶楼梯，需要爬(n-1)阶楼梯和爬(n-2)阶楼梯的方法和。可以使用递归的方法解决这个问题。

    private static int climbStairs(int n) {
        int[] cacheData = new int[n + 1];//将每次爬楼梯数对应的方法数记录下来
        return climbStairsData(n, cacheData);
    }

    private static int climbStairsData(int n, int[] cacheData) {
        if (cacheData[n] > 0) {
            return cacheData[n];
        }
        if (n == 1) {
            cacheData[n] = 1;
        } else if (n == 2) {
            cacheData[n] = 2;
        } else {
            cacheData[n] = climbStairsData(n - 1, cacheData) + climbStairsData(n - 2, cacheData);
        }
        return cacheData[n];
    }

如有不对之处，烦请指出。