用python编写求楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,走完 n 阶台阶共有多少种不同的走法。的程序

递归版本：

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

动态规划版本：

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

其中，dp[i] 表示走到第 i 阶台阶的不同走法数。初始值 dp[1] = 1 和 dp[2] = 2。根据题意，走到第 i 阶台阶有两种情况：从第 i-1 阶台阶走1步上来，或从第 i-2 阶台阶走2步上来。因此，dp[i] = dp[i-1] + dp[i-2]。最终返回 dp[n] 即可。

相关问题

楼梯上有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编写程序计算共有多少种不同的上楼梯方法。

### 回答1：
这是一个经典的动态规划问题。假设f(n)表示上n阶楼梯的不同方法数，那么f(n)可以由f(n-1)和f(n-2)转移而来，因为上n阶楼梯可以从n-1阶楼梯一步上来，也可以从n-2阶楼梯两步上来。因此，f(n) = f(n-1) + f(n-2)。

初始条件是f(1) = 1，f(2) = 2，因为上1阶楼梯只有一种方法，上2阶楼梯有两种方法。

下面是Python代码实现：

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

print(climbStairs(3)) # 输出3，因为有3种方法：1+1+1，1+2，2+1
print(climbStairs(4)) # 输出5，因为有5种方法：1+1+1+1，1+1+2，1+2+1，2+1+1，2+2
print(climbStairs(5)) # 输出8，因为有8种方法：1+1+1+1+1，1+1+1+2，1+1+2+1，1+2+1+1，2+1+1+1，1+2+2，2+1+2，2+2+1

### 回答2：
这个问题可以用动态规划的方法来解决。

我们定义一个数组dp，其中dp[i]表示上到第i阶台阶的不同方法数。根据题目的要求，当i<=2时，dp[i]的值为i。当i>2时，dp[i]的值为dp[i-1]+dp[i-2]，即到达第i阶台阶的不同方法数可以由到达第i-1阶台阶和到达第i-2阶台阶的方法数相加得到。

最终，dp[n]就是我们要求的上楼梯的不同方法总数。

以下是用Python语言编写的程序示例：

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

这个程序的时间复杂度是O(n)，空间复杂度也是O(n)。这意味着，当n非常大时，程序的执行时间和内存占用也会变得非常大。如果需要处理更大的n值，我们可以考虑使用空间复杂度为O(1)的优化算法，例如滚动数组技巧。

### 回答3：
楼梯上有n阶台阶，上楼可以一步上1阶，也可以一步上2阶。我们可以设f(n)为上n阶楼梯的不同方法数。

当n=1时，只有一种方法，即一次走1个台阶，故f(1)=1。
当n=2时，有两种方法，一次走两个或者分两步走，故f(2)=2。
当n=3时，可以一次上1个或2个台阶，所以可以由f(1)和f(2)转移而来，即f(3) = f(2) + f(1) = 3。
当n=4时，可以一次上1个或2个台阶，所以可以由f(2)和f(3)转移而来，即f(4) = f(3) + f(2) = 5。
……
依此类推，可以得到递推公式：

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

其中f(1)=1，f(2)=2。可以使用动态规划的方法，从f(1)和f(2)开始计算直到f(n)。最后得到的f(n)即为上n阶台阶的不同方法数。

下面是Python代码实现：

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

其中，dp为动态规划数组。首先将dp[0]和dp[1]初始化为1和2，然后从2开始循环，每次将dp[i]赋值为dp[i-1]和dp[i-2]的和。最后返回dp[n-1]即为所求。

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

### 回答1：
这道题目可以使用递归的方法来解决。

当楼梯只有1阶台阶时，只有一种走法；当楼梯有2阶台阶时，有两种走法；当楼梯有3阶台阶时，有四种走法。

对于楼梯有n阶台阶的情况，可以分为三种情况：

1. 第一步上1阶台阶，剩下的n-1阶台阶有f(n-1)种走法；

2. 第一步上2阶台阶，剩下的n-2阶台阶有f(n-2)种走法；

3. 第一步上3阶台阶，剩下的n-3阶台阶有f(n-3)种走法。

因此，楼梯有n阶台阶的不同走法数为f(n) = f(n-1) + f(n-2) + f(n-3)。

最终，当楼梯有1阶、2阶、3阶台阶时，分别有1、2、4种不同的走法。

下面是Python代码实现：

def count_ways(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4
else:
return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)

n = int(input("请输入楼梯的阶数："))
ways = count_ways(n)
print("楼梯有%d阶台阶时，共有%d种不同的走法。" % (n, ways))

### 回答2：
这道题目可以使用递归的方法进行求解。假设有 $f(n)$ 种不同的走法来到第 $n$ 阶台阶，则有以下几种情况：

1. 当最后一次跨上一步台阶时，之前则应从第 $n-1$ 阶台阶走上来，共有 $f(n-1)$ 种走法；
2. 当最后一次跨上二步台阶时，之前则应从第 $n-2$ 阶台阶走上来，共有 $f(n-2)$ 种走法；
3. 当最后一次跨上三步台阶时，之前则应从第 $n-3$ 阶台阶走上来，共有 $f(n-3)$ 种走法。

综上所述，$f(n) = f(n-1) + f(n-2) + f(n-3)$。同时需要考虑一下特殊情况：

1. 当 $n = 1$ 时，无论如何只能一步走上来，故 $f(1) = 1$；
2. 当 $n = 2$ 时，有两种情况：一步一步走上来或者一次性跨两步上来，故 $f(2) = 2$；
3. 当 $n = 3$ 时，有四种情况：一步一步走上来、一步两步走上来、两步一步走上来或者一次性跨三步上来，故 $f(3) = 4$。

将上述递推公式和特殊情况带入程序中即可实现计算。

以下是一份 Python 代码实现：

def count_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)

n = int(input("请输入台阶数："))
print("共有 %d 种不同的走法。" % count_ways(n))

输入台阶数后，程序会输出总共有多少种不同的走法。需要注意的是，当 $n$ 较大时，递归计算会非常耗时，因此需要特别注意优化算法。

### 回答3：
首先，我们可以列出递推式f(n)表示爬n阶楼梯的不同走法数目：
f(n) = f(n-1) + f(n-2) + f(n-3)
其中，f(n-1)表示从n-1阶楼梯到达n阶楼梯的走法数目，f(n-2)表示从n-2阶楼梯到达n阶楼梯的走法数目，f(n-3)表示从n-3阶楼梯到达n阶楼梯的走法数目。
当n为1、2、3时，因为没有足够的阶数，只有一种走法，即一步一阶、两阶、三阶。
根据递推式，我们可以通过动态规划的思想，从小到大计算f(1)到f(n)。在每一步计算f(i)时，只需要用到f(i-1)、f(i-2)、f(i-3)三个值，因此可以使用三个变量分别记录这三个值，以节省空间。
最终，f(n)即为所求的走法数目。在计算过程中，需要注意处理边界条件和数据类型溢出等问题，以保证结果正确。