【提高】蜜蜂路线c++

Question

描述

一只蜜蜂在下图所示的数字蜂房上爬动 , 已知它只能从标号小的蜂房爬到标号大的相邻蜂房 , 现在问你：蜜蜂从蜂房 1开始爬到蜂房 N ， 1=<N <=100，有多少种爬行路线？

输入描述

输入 N 的值。（ 1=<n<=100 ）

输出描述

爬行有多少种路线。

用例输入 1

13
用例输出 1

233
来源

递归

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

题目描述：

有一只蜜蜂在数字蜂房上爬行，已知它只能从标号小的蜂房爬到标号大的相邻蜂房。现在问有多少种爬行路线，蜜蜂从蜂房 1 开始爬到蜂房 N，1 <= N <= 100。

输入描述：

输入 N 的值。

输出描述：

输出爬行有多少种路线。

解决方案：

思路：

这个问题本质是一个斐波那契数列问题，即第n个蜂房与第n-1个蜂房和第n-2个蜂房有关。

因此，我们可以用递推的方式求解，也可以用递归的方式求解。

• 递推方式：使用一个数组记住每个蜂房的路径数，然后递推计算当前蜂房的路径数。
• 递归方式：使用递归函数计算当前蜂房的路径数。

代码实现：

• 递推方式：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> dp(n + 1, 0);
    dp[1] = 1;

    for(int i = 2; i <= n; ++i){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;

    return 0;
}

• 递归方式：

#include <iostream>

using namespace std;

int bee_route(int n)
{
    if(n == 1 || n == 2)
        return 1;

    return bee_route(n - 1) + bee_route(n - 2);
}

int main()
{
    int n;
    cin >> n;

    cout << bee_route(n) << endl;

    return 0;
}

时间复杂度：

• 递推方式：O(n)
• 递归方式：O(2^n)