【青蛙跳台阶问题 —— (三种算法）】

青蛙跳台阶问题 —— (三种算法）

• 一.题目介绍
• • 1.1.题目
  • 1.2.图示
  • 二.解题思路
  • 三.题解及其相关算法
  • • 3.1.递归分治法
    • 3.2.动态规划算法（Dynamic Programming）
    • 3.3.斐波那契数列法
    • 四.���意细节

      一.题目介绍

      1.1.题目

      一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

      答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回

      示例 1：

      输入：n = 2

      输出：2

      示例 2：

      输入：n = 7

      输出：21

      示例 3：

      输入：n = 0

      输出：1

      提示：

      0 int con=(int)1e9 + 7; if (n == 1) { return 1; } else if (n == 2) { return 2; } else { return climbStairs(n - 1)%con + climbStairs(n - 2)%con; } } int main() { int n; printf("请输入楼梯的阶数："); scanf("%d", &n); int ways = climbStairs(n); printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways); return 0; } int con = (int)1e9 + 7; if (number == 1) return 1; else if (number == 2) return 2; else { int dp[MAX]; dp[1] = 1; dp[2] = 2; int i = 0; for (i = 3; i dp[i] = dp[i - 1] % con + dp[i - 2] % con; } return dp[number]; } } int main() { int n; printf("请输入楼梯的阶数："); scanf("%d", &n); int ways = climbStairs(n); printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways); return 0; } int con = (int)1e9 + 7; int first = 0; int second = 1; int tem = 0; while (n--) { tem = first + second; first = second % con; second = tem % con; } return first; } int ClimbStairs(int n) { return fbnq(n + 1); } int main() { int n; printf("请输入楼梯的阶数："); scanf("%d", &n); int ways = ClimbStairs(n); printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways); return 0; }