70_爬楼梯

【问题描述】

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

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

【算法设计思想】

1. 定义状态：
   • 状态是指问题的一个特定阶段的状态。对于“爬楼梯”问题，状态可以定义为 dp[i]，表示到达第 i 阶楼梯的方法数。
2. 确定状态转移方程：
   • 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于“爬楼梯”问题，状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]，表示到达第 i 阶楼梯的方法数等于到达第 (i-1) 阶楼梯的方法数加上到达第 (i-2) 阶楼梯的方法数。
3. 初始化：
   • 初始化一些基本情况，以便开始递推计算。对于“爬楼梯”问题，初始化 dp[1] = 1 和 dp[2] = 2，表示到达第1阶楼梯有一种方法，到达第2阶楼梯有两种方法。
4. 确定计算顺序：
   • 确定状态的计算顺序，通常是从已知状态逐步推导到最终状态。对于“爬楼梯”问题，计算顺序是从 i = 3 开始，逐步计算到 i = n。
5. 返回结果：
   • 最后返回所需的最终结果。对于“爬楼梯”问题，返回 dp[n]，即到达第 n 阶楼梯的方法数。

【算法描述】

C++：

class Solution {
public:
    int climbStairs(int n) {
        // 如果楼梯只有1阶，那么只有一种爬法，直接返回1
        if (n == 1) return 1;
        
        // 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2
        if (n == 2) return 2;

        // 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量
        int dp[n + 1];

        // 初始化dp数组的前几个值
        dp[0] = 0; // 从第0阶开始，没有爬法
        dp[1] = 1; // 从第1阶开始，只有一种爬法
        dp[2] = 2; // 从第2阶开始，有两种爬法

        // 从第3阶开始，使用动态规划计算每一阶的爬法数量
        for (int i = 3; i <= n; i++) {
            // 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回到达第n阶的爬法数量
        return dp[n];
    }
};

Java：

class Solution {
    public int climbStairs(int n) {
        // 如果楼梯只有1阶，那么只有一种爬法，直接返回1
        if (n == 1) {
            return 1;
        }
        
        // 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2
        if (n == 2) {
            return 2;
        }

        // 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量
        int[] dp = new int[n + 1];

        // 初始化dp数组的前几个值
        dp[1] = 1; // 从第1阶开始，只有一种爬法
        dp[2] = 2; // 从第2阶开始，有两种爬法

        // 从第3阶开始，使用动态规划计算每一阶的爬法数量
        for (int i = 3; i <= n; i++) {
            // 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回到达第n阶的爬法数量
        return dp[n];
    }
}

Python：

class Solution:
    def climbStairs(self, n: int) -> int:
        # 创建一个大小为n+1的列表dp，用于存储从第0阶到第n阶的爬法数量
        dp = [0] * (n + 1)

        # 如果楼梯只有0阶，根据题目假设，返回0（实际上这种情况可能不需要处理）
        if n == 0:
            return 0
        
        # 如果楼梯只有1阶，那么只有一种爬法，直接返回1
        if n == 1:
            return 1
        
        # 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2
        if n == 2:
            return 2

        # 初始化dp数组的前几个值
        dp[0] = 0  # 从第0阶开始，没有爬法
        dp[1] = 1  # 从第1阶开始，只有一种爬法
        dp[2] = 2  # 从第2阶开始，有两种爬法

        # 从第3阶开始，使用动态规划计算每一阶的爬法数量
        for i in range(3, n + 1):
            # 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量
            dp[i] = dp[i - 1] + dp[i - 2]

        # 返回到达第n阶的爬法数量
        return dp[n]

C：

int climbStairs(int n) {
    // 如果楼梯只有1阶，那么只有一种爬法，直接返回1
    if (n == 1) return 1;
    
    // 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2
    if (n == 2) return 2;

    // 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量
    int dp[n + 1];

    // 初始化dp数组的前几个值
    dp[0] = 0; // 从第0阶开始，没有爬法
    dp[1] = 1; // 从第1阶开始，只有一种爬法
    dp[2] = 2; // 从第2阶开始，有两种爬法

    // 从第3阶开始，使用动态规划计算每一阶的爬法数量
    for (int i = 3; i <= n; i++) {
        // 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 返回到达第n阶的爬法数量
    return dp[n];
}