动态规划爬楼梯问题5个台阶分析方法
时间: 2023-08-11 15:21:20 浏览: 51
对于爬楼梯问题,如果有5个台阶,我们可以采用以下两种方法进行分析。
方法一:暴力枚举
我们可以用暴力枚举的方法来计算爬5个台阶的方案数。假设我们已经爬到了第4个台阶,那么我们可以选择再爬1个台阶,也可以选择再爬2个台阶。因此,到达第5个台阶的方案数就是到达第4个台阶的方案数加上到达第3个台阶的方案数。同理,到达第4个台阶的方案数就是到达第3个台阶的方案数加上到达第2个台阶的方案数。以此类推,到达第3个台阶的方案数是2,到达第2个台阶的方案数是1,到达第1个台阶的方案数是1,因为只有1个台阶,我们只能直接爬到第1个台阶。因此,到达第5个台阶的方案数是 2+1+2+1+1 = 7。
方法二:动态规划
我们可以使用动态规划的方法来计算爬5个台阶的方案数。我们定义一个长度为6的数组dp,dp[i]表示爬到第i个台阶的方案数。因为我们只能每次爬1个或2个台阶,所以到达第i个台阶的方案数就是到达第i-1个台阶的方案数加上到达第i-2个台阶的方案数。因此,我们可以得到以下递推公式:
dp[1] = 1;
dp[2] = 2;
dp[i] = dp[i-1] + dp[i-2];
最后,我们返回dp[5] 即可得到爬到第5个台阶的方案数。
下面是动态规划的C语言代码实现:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n <= 1) {
return 1;
}
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];
}
int main() {
int n = 5;
printf("爬到第%d层楼梯的方案数为:%d\n", n, climbStairs(n));
return 0;
}
```