一个n阶楼梯,你站在底部,每次可以选择走1阶或者2阶,问:你走到楼梯顶部有多少种走法?用c语言做出来
时间: 2024-05-08 16:15:27 浏览: 13
以下是一个递归实现的代码:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
int main() {
int n;
printf("请输入楼梯阶数:");
scanf("%d", &n);
printf("有%d种走法\n", climbStairs(n));
return 0;
}
```
这个代码的思路比较简单,就是递归地求解。当楼梯阶数为1时,只有1种走法;当楼梯阶数为2时,有2种走法;当楼梯阶数大于2时,可以选择先走1阶,然后剩下的n-1阶有climbStairs(n-1)种走法;或者选择先走2阶,然后剩下的n-2阶有climbStairs(n-2)种走法。最终结果就是这两种情况的和。
这个代码的时间复杂度为O(2^n),比较低效。可以使用动态规划来优化,时间复杂度可以降为O(n)。
相关问题
. 一个n阶楼梯,你站在底部,每次可以选择走1阶或者2阶,问:你走到楼梯顶部有多少种走法?
当n=1时,只有一种走法:1步
当n=2时,有两种走法:一次走2步或分两次走每次走1步
当n=3时,有三种走法:第一步走1步,后面有两阶还有两种走法;第一步走2步,后面有一阶还有一种走法
当n=4时,有五种走法:第一步走1步,后面有三阶还有三种走法;第一步走2步,后面有两阶还有两种走法
当n=5时,有八种走法:第一步走1步,后面有四阶还有五种走法;第一步走2步,后面有三阶还有三种走法
以此类推,可以发现,走到n阶楼梯的走法数量,等于走到n-1阶楼梯的走法数量加上走到n-2阶楼梯的走法数量。因此可以使用递归或动态规划来解决该问题。
递归解法:
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
```
动态规划解法:
```python
def climbStairs(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]
```
以上两种解法时间复杂度均为O(n),空间复杂度均为O(n)。也可以使用滚动数组来优化空间复杂度,将空间复杂度降为O(1)。
用c语言一个n阶楼梯,你站在底部,每次可以选择走1阶或者2阶,问:你走到楼梯顶部有多少种走法?
这道题可以使用递归或者动态规划来解决。
1. 递归方法:
递归方法比较简单,可以把问题拆分成子问题。对于一个n阶楼梯,要想到达顶部,可以选择走1阶或者2阶。如果选择走1阶,则剩下的问题就是一个n-1阶的楼梯;如果选择走2阶,则剩下的问题就是一个n-2阶的楼梯。因此,可以使用递归的方式求解:
```c
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
```
2. 动态规划方法:
动态规划的思路是先解决子问题,再通过子问题的解来求解原问题。对于这个问题,可以使用一个数组来保存到达每一个阶梯的走法数量。初始时,到达第1阶和第2阶的走法数量分别为1和2。然后,从第3阶开始,到达当前阶梯的走法数量就是到达前一阶和前两阶的走法数量之和。最后,返回到达第n阶的走法数量即可。
```c
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
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];
}
```