Hello. I tried various ways of writing in my own way.

I would appreciate it if you could refer to it. The following description is a familiar one.

`fib_1.py`

```
def fib(n):
if n == 1:
return 0
if n == 2:
return 1
else:
return fib(n-1) +fib(n-2)
```

I think there is also such a way of writing.

`fib_2.py`

```
def fib(n):
if n == 1 or n == 2:
return n-1
return fib(n-1) +fib(n-2)
```

I was happy to clap my hands because I was able to optimize it for a simple description, There are many duplicate calculations, so I want to optimize it somehow. Prepare a memo by referring to the advice of an expert, It seems that the calculation can be reduced by extracting from the applicable ones.

`fib_3.py`

```
class fib:
def __init__(self):
self.table ={}
def cal(self,n):
if n <= 2:
return n-1
if n in self.table:
return self.table[n]
self.table[n] = self.cal(n-2)+self.cal(n-1)
return self.table[n]
fib_sequence = fib()
```

Recursive + memo, I see. You can also do this. I played with it a little.

`fib_4.py`

```
def fib(n):
if n <= 2:
return n-1
if n in memo:
return memo[n]
memo[n] = fib(n-2)+fib(n-1)
return memo[n]
memo = {}
```

There seems to be an approach called greedy algorithm other than simplifying with memos, It will be done again this time.

Imagine what you want to do It's fun to experiment with different approaches.

Coco also had a method using a for statement. Great!!

If you are in trouble because you can't get an image, lower the level to one rank and I think you should do a preparatory exercise in the article here. It's helpful, this was also a great article.

Recommended Posts