爬楼梯

题目要求

这个问题是一个经典的动态规划问题。给定一个整数 n，代表楼梯的总阶数，你可以一次爬 1 阶或 2 阶。你需要计算出所有不同的爬楼梯的方法数。

解题思路

要解决这个问题，我们可以采用动态规划的方法。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

定义状态： 首先，我们定义 dp[i] 为到达第 i 阶楼梯的方法数。
状态转移方程： 要到达第 i 阶楼梯，有两种方式：从第 i-1 阶爬上一阶，或者从第 i-2 阶爬上两阶。因此，到达第 i 阶的方法数就是到达第 i-1 阶和第 i-2 阶方法数的和，即 dp[i] = dp[i-1] + dp[i-2]。
初始化： 我们知道 dp[1] = 1（只有一种方法爬一阶），dp[2] = 2（有两种方法爬两阶：一次爬两阶或分两次各爬一阶）。
计算顺序： 由于状态转移方程的性质，我们应该从小到大计算 dp 数组。
结果： 最终，dp[n] 就是我们要求的答案，即到达第 n 阶楼梯的方法数。

这个问题也可以用数学的方法来解决，实际上它与斐波那契数列有关。在斐波那契数列中，每一个数都是前两个数的和，这与爬楼梯问题的状态转移方程是一致的。因此，我们也可以用斐波那契数列的递推或者闭合形式的公式来解决这个问题。但在实际编程中，动态规划的方法更为直观和易于实现。

Golang 版本

package main

import "fmt"

func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

func main() {
    n := 10 // 示例，假设楼梯有10阶
    fmt.Println("Total ways to climb:", climbStairs(n))
}

这段代码定义了一个 climbStairs 函数，它接受一个整数 n 作为参数，并返回到达第 n 阶楼梯的方法数。在 main 函数中，我们调用了 climbStairs 函数并打印出结果。这里以楼梯有 10 阶为例。

C++版本

#include <iostream>
#include <vector>

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    std::vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    int n = 10; // 示例，假设楼梯有10阶
    std::cout << "Total ways to climb: " << climbStairs(n) << std::endl;
    return 0;
}

这段代码使用 C++ 编写，实现了与 Golang 版本相同的功能。它定义了一个 climbStairs 函数，用于计算到达楼梯顶部的不同方法数，并在 main 函数中测试了这个函数。

Python 版本

def climb_stairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

if __name__ == "__main__":
    n = 10  # 示例，假设楼梯有10阶
    print(f"Total ways to climb: {climb_stairs(n)}")

这段代码提供了一个 climb_stairs 函数，用于计算爬到楼梯顶部的不同方法数。在 if __name__ == "__main__": 块中，我们调用这个函数并打印出结果，这里以楼梯有 10 阶为例。

Java 版本

public class Solution {

    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10; // 示例，假设楼梯有10阶
        System.out.println("Total ways to climb: " + climbStairs(n));
    }
}

这段 Java 代码定义了一个 climbStairs 方法，用于计算到达楼梯顶部的不同方法数。在 main 方法中，我们调用 climbStairs 方法并打印出结果，这里以楼梯有 10 阶为例。

Rust 版本

fn climb_stairs(n: i32) -> i32 {
    let mut dp = vec![0; (n + 1) as usize];
    dp[1] = 1;
    dp[2] = 2;
    for i in 3..=n as usize {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n as usize]
}

fn main() {
    let n = 10; // 示例，假设楼梯有10阶
    println!("Total ways to climb: {}", climb_stairs(n));
}

这段 Rust 代码实现了一个 climb_stairs 函数，它接受一个 i32 类型的参数 n 并返回一个 i32 类型的结果，表示到达第 n 阶楼梯的方法数。在 main 函数中，我们调用了 climb_stairs 函数并打印出结果，这里以楼梯有 10 阶为例。

总结

上述问题是一个经典的动态规划问题，通常被称为“爬楼梯问题”。解决这个问题的关键在于找到一个递推关系，即每一步的解可以由之前的步骤推导出来。

解法的核心思想是使用一个数组（在某些语言中是列表或向量）来存储到达每一阶楼梯的方法数。这个数组被称为动态规划表（dp table）。

动态规划表的初始化非常重要，通常需要手动设置前几个值。在这个问题中，到达第一阶楼梯有 1 种方法，到达第二阶楼梯有 2 种方法。

状态转移方程是 dp[i] = dp[i-1] + dp[i-2]，它表示到达第 i 阶楼梯的方法数等于到达第 i-1 阶楼梯的方法数加上到达第 i-2 阶楼梯的方法数。这是因为每次你可以爬 1 阶或 2 阶，所以到达第 i 阶的最后一步可以从第 i-1 阶爬 1 阶上来，或者从第 i-2 阶爬 2 阶上来。

在编程实现中，我们遍历从 3 到 n 的每一阶楼梯，并应用状态转移方程来填充动态规划表。最后，dp[n] 就是我们要找的答案，即到达楼顶的方法数。

不同编程语言的实现细节可能有所不同，但核心算法和逻辑是一致的。在 Golang、C++、Python、Java 和 Rust 的代码示例中，我们都定义了一个函数或方法来实现这个算法，并在主函数中调用该函数来获取结果。

hot-100