C语言写出,一个0附楼梯,你站在底部,每次可以选泽走1阶或
时间: 2024-05-13 20:20:30 浏览: 13
2阶,问你到达第n阶台阶共有多少种走法。
以下是代码实现:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int dp[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main() {
int n;
printf("请输入台阶数:");
scanf("%d", &n);
int count = climbStairs(n);
printf("到达第%d阶台阶共有%d种走法。\n", n, count);
return 0;
}
```
该程序通过动态规划的思路实现,先判断特殊情况,然后使用一个数组dp存储每一层台阶的走法数,最后返回n层的走法数即可。
相关问题
用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];
}
```
c语言一个n阶楼梯,你站在底部,每次你可以选择走1阶或者两阶,问:你走到楼梯顶部有多少种走法?
这道题可以使用递归或动态规划来解决。
递归解法:
```
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
```
动态规划解法:
```
int climbStairs(int n) {
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
```
其中,dp数组保存了到达每一阶楼梯的走法总数。初始时,dp[0]和dp[1]都为1,因为到达第0阶和第1阶楼梯只有一种走法,即不走或只走一步。接着,从第2阶楼梯开始,每一阶楼梯的走法总数等于前两阶楼梯的走法总数之和,即dp[i] = dp[i-1] + dp[i-2]。最终,dp[n]就是到达楼梯顶部的走法总数。