古交做网站,网站制作一般怎么收费,住房城乡建设网站官网入口,网页设计培训南京青蛙跳台阶问题是一个经典的递归问题#xff0c;也与斐波那契数列有关。问题是这样的#xff1a;一只青蛙站在一个n阶台阶上#xff0c;它每次可以跳1阶或2阶#xff0c;问青蛙跳到顶端总共有多少种跳法。
这个问题可以用递归或动态规划来解决。以下是使用C实…青蛙跳台阶问题是一个经典的递归问题也与斐波那契数列有关。问题是这样的一只青蛙站在一个n阶台阶上它每次可以跳1阶或2阶问青蛙跳到顶端总共有多少种跳法。
这个问题可以用递归或动态规划来解决。以下是使用C实现的动态规划解法
#include iostream
#include vector// 动态规划解法
int climbStairs(int n) {if (n 2) {return n;}// 创建一个数组来存储子问题的解std::vectorint 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::vectorint来存储子问题的解避免了重复计算。数组dp[i]表示到达第i阶台阶的跳法数。根据题目条件到达第i阶台阶的跳法数等于到达(i-1)阶和(i-2)阶台阶的跳法数之和。
面试回答示例 青蛙跳台阶问题可以通过动态规划来解决。我们首先定义一个数组dp其中dp[i]表示到达第i阶台阶的跳法数。我们知道到达第一阶和第二阶都只有一种方法。对于更高的台阶到达那里的方法数是到达前一阶和前两阶台阶的方法数之和因为青蛙可以选择从这两个位置跳过来。我们从第三阶台阶开始逐步计算直到第n阶最终返回dp[n]作为答案。这种方法避免了递归方法中的重复计算时间复杂度是O(n)空间复杂度也是O(n)。
