假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思路

重要性质：爬 n 楼的方案数 = 爬 n-1 楼的方案数 + 爬 n-2 楼的方案数

解法一：递归+记忆化搜索

在常用的递归方法中，加入一个数组 mem[] 用来记录已经计算过的子问题，避免重复计算

解法二：动态规划 （推荐）

• 定义状态： dp[i] 就是到达第 i 阶的方案数
• 基础情况： n=1 或者 n=2 时，我们直接知道答案
• 转移方程：dp[i] = dp[i-1] + dp[i-2]

Java 实现

动态规划

    public int climbStairs(int n) {
        if (n == 1 || n == 2){
            return n;
        }
        int[] dp = new int[n+1]; // 为了对齐，dp[0]只占位
        dp[1] = 1;
        dp[2] = 2;
        for (int i=3 ; i <= n ; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }