3、 上楼梯问题。 上楼梯走法数:一个楼梯有n个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶，编写一个程序求上楼梯共有多少种不同的走法。

解法一：递归

可以用递归的方法求解。设$f(n)$为上$n$个台阶的不同走法数目，则$f(n) = f(n-1) + f(n-2)$，因为可以从$n-1$个台阶上走一步到$n$，也可以从$n-2$个台阶上走两步到$n$。

需要注意的是，当$n=1$时，只有一种走法；当$n=2$时，有两种走法。

代码如下：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbStairs(n-1) + climbStairs(n-2)

解法二：动态规划

通过递归可以得到答案，但是时间复杂度为$O(2^n)$，效率较低。可以通过动态规划的方式进行优化，将递归的过程转化为自底向上的求解过程。

设$dp[i]$为上$i$个台阶的不同走法数目，则$dp[i] = dp[i-1] + dp[i-2]$。初始状态为$dp[1]=1$，$dp[2]=2$。

代码如下：

def climbStairs(n):
    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]

相关问题

1190：上台阶 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 59792 通过数: 20101 【题目描述】 楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。 【输入】 输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。 【输出】 每一行输出对应一行输入的结果，即为走法的数目。 【输入样例】 1 2 3 4 0 【输出样例】 1 2 4 7

这是一道经典的动态规划问题，可以使用递推公式进行求解。

设 f(n) 表示到第 n 级台阶的不同走法数目，考虑最后一步的情况：

1. 如果最后一步只跨了一级台阶，则前面共有 f(n-1) 种不同的走法；

2. 如果最后一步跨了两级台阶，则前面共有 f(n-2) 种不同的走法；

3. 如果最后一步跨了三级台阶，则前面共有 f(n-3) 种不同的走法。

因此，可以得到递推公式：f(n) = f(n-1) + f(n-2) + f(n-3)。

边界条件为：f(1) = 1, f(2) = 2, f(3) = 4。

以下是代码实现：

用python解答该题目1190：上台阶 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 17719 通过数: 4957 【题目描述】 楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。 【输入】 输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。 【输出】 每一行输出对应一行输入的结果，即为走法的数目。 【输入样例】 1 2 3 4 0 【输出样例】 1 2 4 7

你可以使用递归来解决这个问题。首先定义一个递归函数，输入参数为台阶数n，函数返回值为走法的数目。然后根据题目条件，分为三种情况进行递归计算：

1. 当n为0时，表示没有台阶了，返回0种走法。
2. 当n为1时，只有一阶台阶，返回1种走法。
3. 当n为2时，有两种走法：一步上1阶台阶两次或者一步上2阶台阶一次，返回2种走法。
4. 当n大于2时，可以选择一步上1阶台阶、一步上2阶台阶或者一步上3阶台阶，所以总的走法数目等于上这三种情况的走法数目之和。

下面是用Python实现的代码：

def climb_stairs(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)

while True:
    n = int(input())
    if n == 0:
        break
    print(climb_stairs(n))

希望对你有帮助！如果还有其他问题，请随时提问。