假期里，你准备爬山锻炼，上山的路是很多级台阶，假如你每步可以上一个台阶也可以上两个台阶，请编程求解你有多少种到达第N阶的走法。输入 台阶的级数N。(N<=90) 输出 到达第N阶台阶的走法。

这道题目可以使用斐波那契数列的思想，我们可以把到达第 $i$ 阶台阶的走法总数看做是到达第 $i-1$ 阶台阶的走法总数和到达第 $i-2$ 阶台阶的走法总数之和。不过需要注意的是，当到达第 $1$ 阶台阶的走法总数为 $1$，到达第 $2$ 阶台阶的走法总数为 $2$。

我们可以使用递归实现这个思路，但是由于递归的时间复杂度过高，会导致计算时间过长或者栈溢出。因此，我们可以使用递推的方式实现，即从 $1$ 阶和 $2$ 阶开始，一步一步推导到 $N$ 阶。

下面是 Python 代码实现：

def climb_stairs(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # 初始化到达第 1 阶和第 2 阶的走法总数
    f1, f2 = 1, 2

    # 从第 3 阶开始递推
    for i in range(3, n + 1):
        f3 = f1 + f2  # 计算到达第 i 阶的走法总数
        f1, f2 = f2, f3  # 更新 f1 和 f2
    return f3

这样，我们就可以用 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度求解这个问题了。

相关问题

假期里，你准备爬山锻炼，上山的路是很多级台阶，假如你每步可以上一个台阶也可以上两个台阶，请编程求解你有多少种到达第N阶的走法。

好的，这是一个经典的动态规划问题。我们可以用一个数组 $dp$ 来记录到达每个台阶的走法总数。假设 $dp[i]$ 表示到达第 $i$ 级台阶的走法总数，那么有如下转移方程：

$$dp[i] = dp[i-1] + dp[i-2]$$

初始值为 $dp[1]=1$ 和 $dp[2]=2$。

根据转移方程，我们可以写出如下的 Python 代码来求解：

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

当然，我们也可以将空间复杂度优化到 $O(1)$，只需要用两个变量来记录 $dp[i-1]$ 和 $dp[i-2]$ 的值即可。

用c++实现一个顽猴在一座有30级台阶的小山上爬山跳跃。猴子上山一步可跳1级，或跳3级。试求上山的30级台阶有多少种不同的爬法。

这是一个经典的动态规划问题，通常被称为“斐波那契兔子”或“阶梯问题”。我们可以用一个二维数组 `dp` 来记录每一步的不同爬法，其中 `dp[i]` 表示到达第 `i` 阶台阶的所有可能路径数。对于每一步，猴子有两种选择：要么跳一级，要么跳三级。因此，我们通过更新 `dp[i]` 的值来累加之前两步的情况。

以下是简单的 C++ 实现：

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int dp[n + 1];  // 初始化数组，假设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];
}

int main() {
    int steps = 30;
    cout << "爬上 " << steps << " 级台阶的不同爬法共有 " << climbStairs(steps) << " 种。\n";
    return 0;
}

当调用 `climbStairs(30)`，程序将返回30阶台阶的总爬法数量。