您的位置:首页 > 房产 > 建筑 > C++算法-青蛙跳台阶【面试】

C++算法-青蛙跳台阶【面试】

2024/12/23 9:46:36 来源:https://blog.csdn.net/xy18990/article/details/139653791  浏览:    关键词:C++算法-青蛙跳台阶【面试】

"青蛙跳台阶"问题是一个经典的递归问题,也与斐波那契数列有关。问题是这样的:一只青蛙站在一个n阶台阶上,它每次可以跳1阶或2阶,问青蛙跳到顶端总共有多少种跳法。

这个问题可以用递归或动态规划来解决。以下是使用C++实现的动态规划解法:

#include <iostream>
#include <vector>// 动态规划解法
int climbStairs(int n) {if (n <= 2) {return n;}// 创建一个数组来存储子问题的解std::vector<int> dp(n + 1, 0);// 初始化前两个台阶的跳法dp[1] = 1;dp[2] = 2;// 计算从3阶到n阶的跳法for (int i = 3; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}// 返回n阶台阶的跳法总数return dp[n];
}int main() {int n = 5;std::cout << "Number of ways to climb " << n << " steps is: " << climbStairs(n) << std::endl;return 0;
}

这段代码中,climbStairs函数使用了一个std::vector<int>来存储子问题的解,避免了重复计算。数组dp[i]表示到达第i阶台阶的跳法数。根据题目条件,到达第i阶台阶的跳法数等于到达(i-1)阶和(i-2)阶台阶的跳法数之和。

面试回答示例:
"青蛙跳台阶问题可以通过动态规划来解决。我们首先定义一个数组dp,其中dp[i]表示到达第i阶台阶的跳法数。我们知道到达第一阶和第二阶都只有一种方法。对于更高的台阶,到达那里的方法数是到达前一阶和前两阶台阶的方法数之和,因为青蛙可以选择从这两个位置跳过来。我们从第三阶台阶开始,逐步计算直到第n阶,最终返回dp[n]作为答案。这种方法避免了递归方法中的重复计算,时间复杂度是O(n),空间复杂度也是O(n)。"

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com