I have a real function V taking its values in S*{1,...,N} where S is a finite set containing elements of the form (s_0,s_1), where s_0,s_1 are reals. V follows an "induction formula" of the following form : V(s,n)=max_{a in A} f(s,a,n)+V(g(s,a,n),n+1) and V(s,N)=0 for any s, for a given finite set A and two functions f and g. g is a function that returns an element of S, and f returns a real.
I would like to implement a function in Python to compute V((0,1),0). I wanted to do this by updating an array of size (|S|,N) via the induction formula, but the problem that I have is that I see no "good" way of accessing the index corresponding to g(s,a,n) in my array at each step. The only thing I can think of is to sort my initial set S and then access the aforementioned index through the use of bisect.bisect(), but since I would have to do this at every step this would be quite costly. Is there a better way to do this in general, with no knowledge on what the function g is ?
You could use functools.cache (Python >= 3.9). This is an optimization technique that allows you to store the results of an expensive function call and return the cached result when the same inputs occur again.
This decorator makes use of a mapping instead of an array.
from functools import cache
@cache
def V(s, n):
if n == N:
return 0
return max(f(s, a, n) + V(g(s, a, n), n + 1) for a in A)