fibonacci2.md

# Python 斐波那契(fibonacci)(II)

斐波那契的递归实现版本里面有很多冗余计算，可以通过增加缓存来优化。

```python
def fibonacci_inner(n, cache):
    if n == 1 or n == 2:
        return 1
    
    r = 0
    
    # TODO(You): 实现缓存


def fibonacci(n):
    return fibonacci_inner(n, {})

if __name__ == '__main__':
    print(fibonacci(6))
```

请选出下面的 Python 斐波那契的缓存优化实现代码中，<span style="color:red">错误</span> 的选项。

## template

```python
def fibonacci_inner1(n, cache):
    if n == 1 or n == 2:
        cache[0] = 1
        cache[1] = 1
        return 1

    if cache.get(n) is None:
        fibonacci_inner1(n-2, cache)
        fibonacci_inner1(n-1, cache)
        cache[n-1] = cache[n-2]+cache[n-3]

    return cache[n-1]


def fibonacci1(n):
    return fibonacci_inner1(n, {})


if __name__ == '__main__':
    print(fibonacci1(10))
```

## 答案

```python
if cache.get(n) is None:
    fibonacci_inner1(n-2, cache)
    fibonacci_inner1(n-1, cache)
    cache[n] = cache[n-1]+cache[n-2]
return cache[n]
```

## 选项

### A

```python
if cache.get(n) is None:
    cache[n-2] = fibonacci_inner1(n-2, cache)
    cache[n-1] = fibonacci_inner1(n-1, cache)
    cache[n] = cache[n-1]+cache[n-2]
return cache[n]
```

### B

```python
if cache.get(n) is not None:
    return cache[n]
else:
    cache[n] = fibonacci_inner1(n-1, cache) + fibonacci_inner1(n-2, cache)
    return cache[n]
```

### C

```python
if cache.get(n) is  None:
    cache[n] = fibonacci_inner(n-2, cache) + fibonacci_inner(n-3, cache)
return cache[n]
```