一共有n阶台阶，一次只能上1阶或2阶台阶，问上n阶台阶一共有多少种方法？请使用动态规划方法实现，编写最优解的递推公式、计算最优值的程序代码。

好的，这是一道经典的动态规划问题。假设到达第i阶台阶的方法有f(i)种，那么f(i)可以由f(i-1)和f(i-2)转移而来。当然，当i=1或2时，f(1)=1, f(2)=2。因为只能上1阶或2阶台阶。

因此，递推公式为：

f(i) = f(i-1) + f(i-2) (i>2)

程序代码实现如下：

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        f1 = 1
        f2 = 2
        for i in range(3, n+1):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3

这个算法的时间复杂度是O(n)，空间复杂度是O(1)。

相关问题

有n步台阶，一次只能上1步或2步，共有多少种走法。用c语言编程

下面是用递归法实现的C语言代码：

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1 || n == 2) {
        return n;
    } else {
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

int main() {
    int n;
    printf("请输入台阶数：");
    scanf("%d", &n);
    printf("共有%d种走法\n", climbStairs(n));
    return 0;
}

也可以用非递归的动态规划方法实现，代码如下：

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    int dp[n];
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}

int main() {
    int n;
    printf("请输入台阶数：");
    scanf("%d", &n);
    printf("共有%d种走法\n", climbStairs(n));
    return 0;
}

一只青蛙跳台阶一次可以跳1阶可以跳2阶，台阶为n时有多少种跳法

这道题可以用动态规划的思想来解决。考虑青蛙跳到第 n 级台阶，它可以从第 n-1 级台阶跳上来，也可以从第 n-2 级台阶跳上来。因此，如果设 dp(n) 表示跳到第 n 级台阶的跳法总数，那么有：

dp(n) = dp(n-1) + dp(n-2)

初始值为 dp(1) = 1，dp(2) = 2。因为只有一级台阶时只能跳一步，两级台阶时可以跳两步或分两次跳一步。

最终的答案就是 dp(n)。可以使用循环来依次计算 dp(3) 到 dp(n)。时间复杂度为 O(n)。

下面是示例代码：

def jump(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    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]

当 n=3 时，结果为 3；当 n=4 时，结果为 5；当 n=5 时，结果为 8，以此类推。