暴力法
思路：
按照函数调用的递归树,记录符合条件的跳跃操作：
python代码：
class Solution:
def __init__(self):
self.solutions = 0
pass
def jump(self, start, end):
if start > end:
return 0
elif start == end:
return 1
return self.jump(start + 1, end) + self.ju
这个问题是经典的动态规划问题，通常被称为“青蛙跳台阶”或者“斐波那契数列”的变种。我们来深入分析一下解题思路。
题目描述了一只青蛙要跳上n级台阶，每次它可以跳1级或2级。我们要找出青蛙跳上n级台阶的所有可能方法数。这是一个组合问题，因为每一步都有两种选择（跳1级或2级），而这些选择是相互独立的。
### 暴力法
暴力法，也称为递归法，直接通过递归的方式来解决问题。如代码所示，定义一个`jump`函数，计算从`start`到`end`的台阶有多少种跳法。当`start`等于`end`时，返回1（表示到达目标），否则递归计算`jump(start+1, end)`和`jump(start+2, end)`的和。这种方法的缺点是存在大量的重复计算，导致效率低下，时间复杂度为O(2^n)。
```python
class Solution:
def __init__(self):
self.solutions = 0
def jump(self, start, end):
# ... (与给出的代码一致)
```
### 动态规划优化
为了提高效率，我们可以使用动态规划的方法，将已经计算过的状态存储起来，避免重复计算。这里我们用一个列表`mem`来保存已计算的台阶数目的跳法。`mem[start]`表示跳到`start`台阶的方法数。初始时，`mem[0]`为1（表示没有跳就到达了0台阶），`mem[1]`和`mem[2]`分别为1和2（分别对应跳1级和2级）。然后对于每个`i >= 3`，`mem[i]`等于`mem[i-1]`和`mem[i-2]`的和。这样，我们只需要遍历一次数组，就能得到所有台阶的跳法。时间复杂度降为O(n)，空间复杂度也为O(n)。
```python
class Solution:
def __init__(self):
self.solutions = 0
self.mem = []
def jump(self, start, end):
# ... (与给出的代码一致)
```
### 公式法
另外，这个问题实际上与斐波那契数列有紧密联系。前两个台阶的跳法分别是1和2，之后的每个台阶的跳法数都是前两个台阶跳法数的和。因此，我们可以直接用斐波那契数列的公式来求解，避免了递归和动态规划中的重复计算。对于第n个台阶，跳法数就是第n-1个台阶和第n-2个台阶的跳法数之和。我们可以预先计算出前几个台阶的跳法，然后用一个循环来填充剩余的台阶。这种方法的时间复杂度为O(1)，因为只需要一次性计算，空间复杂度为O(n)。
```python
class Solution:
def jumpFloor(self, number):
res = [0, 1, 2]
while len(res) <= number:
res.append(res[-1] + res[-2])
return res[number]
```
如果只记录长度为`number`时的方案数，空间复杂度可以降低到O(1)，因为只需要存储最后两个值即可计算下一个值。
总结，解决“青蛙跳台阶”问题，可以采用暴力递归、动态规划和斐波那契数列公式法。递归法虽然直观但效率低，动态规划和公式法则提供了更优的解决方案。在实际编程中，我们通常会选择时间复杂度和空间复杂度更低的算法来提高程序的性能。
- 1
- 2
前往页