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)
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))