爬楼梯。题目内容:可爱的小明特别喜欢爬楼梯,他有的时候一次爬一个台阶,有的时候一次爬两个台阶,有的时候一次爬三个台阶。如果这个楼梯有n个台阶,小明一共有多少种爬法呢?n值从键盘输入。 输入格式:输入一个整数n,(1<=n<46)。 输出格式:输出当楼梯阶数是n时的上楼方式总数。 输入样例:1 输出样例:1 输入样例:4 输出样例:7 输入样例:24 输出样例:1389537如何用c语言写出来
时间: 2024-02-09 17:09:02 浏览: 149
蓝桥杯训练营第一周作业.pdf
这是一个经典的动态规划问题,可以用递归或迭代的方式实现。以下是用迭代的方式实现:
```c
#include <stdio.h>
int climbStairs(int n) {
int dp[3] = {1, 1, 2}; // dp数组存储每一步的结果
for (int i = 3; i <= n; i++) {
dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3] + dp[(i - 3) % 3];
}
return dp[n % 3];
}
int main() {
int n;
scanf("%d", &n);
printf("%d\n", climbStairs(n));
return 0;
}
```
上述代码中,用 `dp` 数组存储每一步的结果,`dp[i]` 表示爬到第 `i` 级台阶的总爬法数。因为每次只需要用到前三个状态,所以用三个变量存储即可,避免了使用一个数组的空间浪费。最后返回 `dp[n]` 即可得到结果。
阅读全文