请解释一下这段代码：class Solution: res_dict = dict() def fib(self, n: int) -> int: if n == 0: return 0 if n == 1: return 1 if n in self.res_dict: return self.res_dict[n] res = self.fib(n-1) + self.fib(n-2) self.res_dict[n] = res return res

这是一个求斐波那契数列第n项的递归算法，并且使用了动态规划的思想来减少重复计算。

代码解释如下：

1. 定义一个名为Solution的类。

2. 在类中定义一个名为res_dict的类变量，该变量是一个字典，用于保存已经计算过的斐波那契数列数字以避免重复计算。

3. 定义一个名为fib的方法，该方法接收一个整数参数n，并返回斐波那契数列中第n项的值。

4. 首先判断n是否为0或1，如果是则直接返回相应的结果。

5. 然后判断字典中是否已经计算过了第n项，如果是则直接返回字典中保存的结果。

6. 如果字典中没有保存第n项的结果，则递归调用fib方法来计算第n-1项和第n-2项，并将它们相加得到第n项的结果。

7. 将第n项的结果保存在字典中，并返回该结果。

这个算法的时间复杂度为O(n)，因为每个斐波那契数列数字只需要计算一次，空间复杂度也为O(n)，因为需要保存所有已经计算过的结果。使用动态规划的思想可以大大优化算法的性能，特别是对于大的n值。

相关问题

解释代码： def __len__(self): return len(self.wave_dict)

这段代码定义了一个类的方法 `__len__`，该方法返回 `self.wave_dict` 的长度。`self` 是一个类的实例，即对象本身，`wave_dict` 是该对象的一个属性。因此，这个方法返回该对象中 `wave_dict` 属性的长度。

def __init__(self) -> None: self.dict = {}

这段代码是一个类的构造函数 `__init__()` 的定义。在 Python 中，`__init__()` 方法是一个特殊的方法，用于在创建类的实例时进行初始化操作。

在这个例子中，`__init__()` 方法被定义为类的构造函数。它接受一个参数 `self`，它是一个指向实例本身的引用。`self` 参数在类的方法中必须作为第一个参数出现。

在构造函数中，使用 `self.dict = {}` 的语句创建了一个空字典。`self.dict` 是类的一个成员变量，可以在类的其他方法中使用。

构造函数通常用于设置对象的初始状态或执行其他必要的初始化任务。当你创建类的实例时，构造函数会自动调用，并可以在实例化过程中为对象提供必要的属性和状态。

下面是一个示例，展示了如何创建类的实例并访问成员变量：

class MyClass:
    def __init__(self):
        self.dict = {}

obj = MyClass()  # 创建类的实例
obj.dict["key"] = "value"  # 访问成员变量并设置值
print(obj.dict)  # 打印成员变量的值

输出结果将是 `{'key': 'value'}`，表示成功访问并设置了成员变量的值。