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

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

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

      一.题目介绍

      1.1.题目

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

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

      示例 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;}