青蛙跳台阶问题 - JZ08

题目描述

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

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

数据范围： 1 ≤ n ≤ 100

示例：

• 输入：n = 2

• 输出：2

• 解释：有两种跳法：

  • 1级 + 1级
  • 2级

• 输入：n = 7

• 输出：21

解题思路

这是一道典型的动态规划问题，本质上是斐波那契数列的变种：

状态定义：

• f(n) = 跳上n级台阶的总跳法数

状态转移：

• 要跳到第n级台阶，青蛙可以：
  • 从第(n-1)级跳1步到达：有f(n-1)种方法
  • 从第(n-2)级跳2步到达：有f(n-2)种方法
• 因此：f(n) = f(n-1) + f(n-2)

边界条件：

• f(1) = 1（只能跳1级）
• f(2) = 2（跳1+1 或 跳2）

与斐波那契的关系：

• 如果F(n)是标准斐波那契数列（F(1)=1, F(2)=1）
• 那么跳台阶问题的答案是F(n+1)

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 可能用到的辅助类型定义
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现以下函数：

• jumpFloor(n int) int - 主要实现

可选实现多种解法：

• jumpFloorRecursive(n int) int - 递归法
• jumpFloorDP(n int) int - 动态规划
• jumpFloorOptimized(n int) int - 空间优化DP
• jumpFloorMatrix(n int) int - 矩阵快速幂

2. 运行测试

# 运行单元测试
go test -v

# 运行基准测试
go test -bench=.

3. 检查代码格式

# 格式化代码
go fmt ./...

# 代码检查
go vet ./...

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
朴素递归	O(2^n)	O(n)	指数级时间，大量重复计算
动态规划	O(n)	O(n)	自底向上计算
空间优化DP	O(n)	O(1)	只保存必要状态
矩阵快速幂	O(log n)	O(1)	最快的算法

知识点

• 动态规划的基本思想
• 状态定义和状态转移
• 递归与迭代的转换
• 空间复杂度优化
• 取模运算
• 矩阵快速幂

扩展思考

1. 变种问题： 如果青蛙每次可以跳1级、2级或3级，该如何解决？
2. 大数处理： 当n很大时，如何避免整数溢出？
3. 实际应用： 这类问题在实际中有什么应用场景？
4. 优化策略： 在什么情况下选择矩阵快速幂？

注意事项

1. 取模操作： 结果需要对1000000007取模
2. 边界条件： 正确处理n=1和n=2的情况
3. 整数溢出： 在计算过程中注意溢出问题
4. 效率考虑： 对于大的n值，选择合适的算法