f(n)=max{f(j)+f(n−j)+j}
Let f be a function from the set of positive integers to the set of non-negative integers such that f(1)=0 and f(n) is defined as of above for n≥2. Determine the value of f(2020).
Note: The maximum in the definition of f(n) is considered over all j such that 1≤j≤n−1, i.e for all j for which f(n) and f(n−j) are defined.
f(2020) = 2039190
f(n) = n*(n-1)/2
I made a little recursive program in Python which worked fine but started to choke at about n=18 due to all the recursion calls.
So I added a dictionary to store values for f(n) as the became known. Much faster..
my_dictionary = {1:0}
def f(n):
if n == 1:
return 0
else:
if n in my_dictionary:
return my_dictionary[n]
else:
my_max = 0
for j in range(1,n): # this will go from 1 to n-1
test = f(j)+f(n-j)+j
my_max = max(my_max,test)
my_dictionary[n] = my_max
return my_max
Edited on September 3, 2020, 8:47 am
|
|
Posted by Larry
on 2020-09-03 08:41:56 |
Solution.
