C语言白那些可爱的小明特别喜欢爬楼梯,他有的时候一次爬一个台阶,有的时候一次爬两个台阶,有的时候一次爬三个台阶。如果这个楼梯有n个台阶,小明一共有多少种爬法呢?n值从键盘输入。
时间: 2024-03-14 15:44:34 浏览: 183
这个问题可以通过动态规划的方法来解决。我们可以定义一个大小为n+1的数组dp,其中dp[i]表示爬到第i个台阶的方法数。
对于第i个台阶,小明可以从第i-1个台阶,第i-2个台阶或者第i-3个台阶爬上来,所以有以下的状态转移方程:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
初始状态为dp[1]=1,dp[2]=2,dp[3]=4。
最终的答案为dp[n],即小明爬到第n个台阶的方法数。
以下是C语言的代码实现:
```
#include <stdio.h>
int main() {
int n;
printf("请输入台阶数:");
scanf("%d", &n);
int dp[n+1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
printf("小明爬到第%d个台阶的方法数为:%d\n", n, dp[n]);
return 0;
}
```
阅读全文