## Lekcja – Techniki przyśpieszenia programu: memorization & tabulation

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

fib(40)

def fib_mem(n, lookup):
if n <= 2:
lookup[n] = 1

if lookup[n] == 0:
lookup[n] = fib_mem(n-1, lookup) + fib_mem(n-2, lookup)

return lookup[n]

lookup = [0] * 1001

fib_mem(1000, lookup)

def fib_tab(n):

results = [1, 1]

for i in range(2, n):
results.append(results[i-1] + results[i-2])

return results[-1]

fib_tab(1000)
```

## Rozwiązanie

```def get_cheese(table, start, end, day) :
tab_result = []

n = len(table[start:end])
if n == 1 :
return day * table[start], table[start:end]

left, left_tab = get_cheese(table,start+1,end, day+1)
left += day*table[start]
right, right_tab = get_cheese(table, start, end-1, day+1)
right+= day*table[end-1]

if left >= right:
tab_result.append(table[start])
tab_result.extend(left_tab)
return left, tab_result
else:
tab_result.append(table[end-1])
tab_result.extend(right_tab)
return right, tab_result

table = [1,8,4,6,7,5,2,4,1,8,4,6,7,5,2,4,1,8,4,6,7,5]
print(get_cheese(table,0,len(table), 1))

def get_cheese_mem(table,start,end, day, mem):

if mem[day-1][start][end-1] != None:
return mem[day-1][start][end-1]

tab_result = []

n = len(table[start:end])
if n == 1 :
mem[day-1][start][end-1] = [day * table[start], table[start:end]]
return [day * table[start], table[start:end]]

left, left_tab = get_cheese_mem(table,start+1,end, day+1, mem)
left += day*table[start]
right, right_tab = get_cheese_mem(table, start, end-1, day+1, mem)
right+= day*table[end-1]

if left >= right:
tab_result.append(table[start])
tab_result.extend(left_tab)
mem[day-1][start][end-1] = left, tab_result
return left, tab_result

else:
tab_result.append(table[end-1])
tab_result.extend(right_tab)
mem[day-1][start][end-1] = right, tab_result
return right, tab_result

table = [1,8,4,6,7,5,2,4,1,8,4,6,7,5,2,4,1,8,4,6,7,5]
mem = [[[None for day in range(len(table))] for s in range(len(table)) ] for e in range(len(table))]
print(get_cheese_mem(table,0,len(table), 1, mem))

```