leetcode70爬楼梯 -- java

找规律，找到规律以后用函数表达式表示出来即可可以从斐波那契数列得到相应启发，使用动态规划来书写 代码实现

class Solution {
    // 备忘录,用一个数组来进行相应存取
    int[] memo;
    public int climbStairs(int n) {
        
        memo = new int[n + 1];
        return dp(n);
    // 写法其实是一样的
    }

    // 定义：爬到第n级台阶的方法个数为 dp(n) 
    int dp(int n){
        // base case
        if(n <= 2){
            return n;
        }
        if(memo[n] > 0){
            return memo[n];
        }
        // 状态转移方程
        memo[n] = dp(n - 1) + dp(n - 2);
        return memo[n];
    }
}