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.
I tried w/o the computer.... (I post just for illustration, in case anyone is curious)
j f(n) = max{f(j)+f(n-j)+j}, all pos j < n
--------------------------------------------------------------------------
{} f(1) = 0 (by defn)
{1} f(2) = max{(0 + 0 + 1)} = 1
{1,2} f(3) = max{(0 + 1 + 1),(1 + 0 + 2)} = 3
{1,2,3} f(4) = max{(0 + 3 + 1),(1 + 1 + 2),(3 + 0 + 3)} = 6
{1,2,3,4) f(5) = max{(0 + 6 + 1),(3 + 3 + 2),(6 + 1 + 3),(6 + 0 + 4)} = 10
The "max" stuff is overkill. The j = n-1 element defines the recursion:
f(n) <--- f(n-1) + n-1
Edited on September 3, 2020, 11:25 pm
agreed
