假设有2种上楼梯的步伐:1个台阶/步,2个台阶/步。从1楼到2楼有n级台阶。有多少种不同的走法。 输入一行,一个整数n,n<30,表示台阶数。 编写程序,输出一行,一个整数,表示不同走法的个数。
时间: 2024-01-17 07:04:18 浏览: 32
这道题是一个典型的动态规划问题,可以使用递归或者迭代的方法求解。
首先考虑递归的方法,假设函数 f(n) 表示从第 n 个台阶到第 2 个台阶的不同走法数目,那么 f(n) = f(n-1) + f(n-2),因为第 n 个台阶只能从第 n-1 或者 n-2 个台阶走上来。边界条件为 f(1) = 1, f(2) = 2,因为从第 1 个台阶只能跨 1 步到达第 2 个台阶,从第 2 个台阶可以跨 1 步或者 2 步到达第 3 个台阶。
下面是使用递归的 Python 代码:
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
n = int(input())
print(climbStairs(n))
```
但是上面的递归方法效率较低,存在大量的重复计算。可以使用迭代的方法,使用一个数组存储中间结果,避免重复计算。
下面是使用迭代的 Python 代码:
```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]
n = int(input())
print(climbStairs(n))
```
以上代码中使用了一个数组 dp,dp[i] 表示从第 i+1 个台阶到第 2 个台阶的不同走法数目。初始化 dp[0] = 1,dp[1] = 2,然后使用迭代的方法,dp[i] = dp[i-1] + dp[i-2],最后返回 dp[n-1] 即可。