70 爬楼梯

一、题目

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

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

二、题解

思路： 动态规划。设 nums[i] 为爬到第 i 阶的方法数。由于每次只能爬 1 或 2 阶，到达第 i 阶只能从第 i-1 阶跨一步或从第 i-2 阶跨两步上来，故状态转移方程为 nums[i] = nums[i-1] + nums[i-2]。初始化 nums[1] = 1、nums[2] = 2，从第 3 阶递推到第 n 阶即可。

class Solution {
    public int climbStairs(int n) {
        // 【处理边界情况/基础情况】
        // 如果楼梯只有 1 阶，只有 1 种方法（爬 1 阶）
        // 如果楼梯有 2 阶，有 2 种方法（爬两个 1 阶，或直接爬 1 个 2 阶）
        if(n <= 2) return n;

        // 【定义动态规划数组】
        // nums[i] 代表爬到第 i 阶楼梯一共有多少种不同的方法。
        // 数组大小设为 n + 1 是为了让数组的索引 i 直接对应楼梯的阶数，方便理解
        int[] nums = new int[n+1];

        // 【初始化基础状态】
        nums[1] = 1; // 爬到第 1 阶有 1 种方法
        nums[2] = 2; // 爬到第 2 阶有 2 种方法

        // 【状态转移方程】
        // 从第 3 阶开始递推，直到第 n 阶
        for(int i = 3; i <= n; i++) {
            // 核心逻辑：
            // 因为每次只能爬 1 阶或 2 阶，所以到达第 i 阶只有两种可能：
            // 1. 从第 i-1 阶跨 1 步上来 -> 这种走法有 nums[i-1] 种
            // 2. 从第 i-2 阶跨 2 步上来 -> 这种走法有 nums[i-2] 种
            // 因此，到达第 i 阶的总方法数 = 到达第 i-1 阶的方法数 + 到达第 i-2 阶的方法数
            nums[i] = nums[i-1] + nums[i-2];
        }

        // 返回爬到第 n 阶的总方法数
        return nums[n];
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

评论