爬楼梯：从递推关系到动态规划

核心结论#

到达第 n 阶的最后一步要么跨 1 阶、要么跨 2 阶，因此方案数满足 f(n) = f(n - 1) + f(n - 2)。只需要保留前两个状态，空间可以从 O(n) 降为 O(1)。

问题#

每次可以爬 1 或 2 个台阶，计算到达第 n 阶的不同方法数。例如 n = 3 时有 1+1+1、1+2、2+1 三种方法。

状态推导#

• f(1) = 1。
• f(2) = 2。
• 当 n >= 3 时，最后一步的两种情况互斥且覆盖全部方案，所以方案数相加。

Java 实现#

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int previous = 1;
        int current = 2;
        for (int step = 3; step <= n; step++) {
            int next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}

正确性与复杂度#

递推式按最后一步划分所有方案，不重不漏。循环从已知的 f(1)、f(2) 开始，逐步计算到 f(n)。

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

验证#

n = 1、2、3 时结果应分别为 1、2、3。再用较大输入确认循环边界和整数范围符合题目约束。

参考#

• LeetCode 70：爬楼梯