爬楼梯问题c
时间: 2024-02-18 09:04:04 浏览: 27
好的,爬楼梯问题是经典的动态规划问题,题目描述为:假设你正在爬楼梯,楼梯有 n 阶台阶,每次你可以爬 1 阶或 2 阶,那么你有多少种不同的方法可以爬到楼梯顶部?
解题思路:这是一道典型的动态规划问题,我们可以用 dp[i] 表示爬到第 i 阶楼梯的不同方法数,根据题目要求,到达第 i 阶楼梯有两种方法:从第 i-1 阶楼梯爬一阶或从第 i-2 阶楼梯爬两阶。因此,dp[i] = dp[i-1] + dp[i-2],边界条件为 dp[0] = 1,dp[1] = 1。最终答案为 dp[n]。
以下是 C++ 代码实现:
```c++
int climbStairs(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
```
相关问题
动态规划爬楼梯问题C语言代码
好的,下面是一个简单的动态规划爬楼梯问题的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;
}
```
在这个代码中,我们定义了一个 `climbStairs` 函数,这个函数接收一个参数 `n`,表示要爬到第 `n` 层楼梯的方案数。首先判断如果 `n` 小于等于1,则只有一种方案,直接返回1。接着定义一个长度为 `n+1` 的数组 `dp`,用于存储不同层数的方案数。初始化 `dp[0]` 和 `dp[1]` 为1,然后用循环计算出从第2层到第n层的方案数,最后返回 `dp[n]` 即可。
在 `main` 函数中,我们测试了一个 `n` 等于5的例子,输出了爬到第5层楼梯的方案数。
c语言递归函数解决爬楼梯问题
好的,针对你的问题,我可以给出一个使用递归函数解决爬楼梯问题的示例代码:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n <= 2) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
int main() {
int n = 5;
int ways = climbStairs(n);
printf("爬 %d 级楼梯的方法数为 %d\n", n, ways);
return 0;
}
```
在这个示例代码中,`climbStairs` 函数接受一个整数参数 `n`,表示要爬的楼梯的级数。如果 `n` 小于等于 2,则直接返回 `n`,因为在这种情况下爬楼梯的方法数就是 `n`。否则,使用递归调用计算爬 `n - 1` 级楼梯和爬 `n - 2` 级楼梯的方法数,并将它们相加作为爬 `n` 级楼梯的方法数返回。
在 `main` 函数中,我们将 `n` 设置为 5,然后调用 `climbStairs` 函数计算爬 5 级楼梯的方法数,并将结果输出到控制台上。
需要注意的是,使用递归函数解决爬楼梯问题的效率并不高,因为在递归调用的过程中会重复计算很多中间结果。为了提高效率,我们可以使用动态规划等其他算法来解决这个问题。
相关推荐
![cs](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)