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
时间: 2024-03-19 22:42:28 浏览: 14
这是一道经典的动态规划问题,可以使用递推公式进行求解。
设 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实现的代码:
```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))
```
希望对你有帮助!如果还有其他问题,请随时提问。
爬楼梯 题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 输入: 楼梯数n 输出: 方法数 示例输入 示例输出 2 2 3 3 1 1 4 5
这是一个经典的动态规划问题,可以使用递归或者迭代的方式来解决。
递归解法:
当n=1时,只有一种方法,返回1;当n=2时,有两种方法,返回2;当n>2时,可以选择爬1个台阶或者2个台阶,所以爬到第n个台阶的方法数就是爬到第n-1个台阶的方法数加上爬到第n-2个台阶的方法数。因此可以使用递归的方式来解决:
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return climbStairs(n-1) + climbStairs(n-2)
```
迭代解法:
由于递归解法存在大量的重复计算,可以使用迭代的方式来优化。使用一个数组来保存每个台阶的方法数,初始值为[1, 2],然后从第三个台阶开始,每个台阶的方法数就是前两个台阶的方法数之和。
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
dp = [1, 2]
for i in range(2, n):
dp.append(dp[i-1] + dp[i-2])
return dp[-1]
```