Tabulation (Dynamic Programming) using Decorator

Question

Find the Factorial of a number by tabulation using decorators

def factorial(n):
    if n<1:
        return 1
    else:
        f=[0]*(n+1)           #creation of the array/list#
        f[0]=1                #initialization#
        for i in range(1,n+1):#the loop#
            f[i]=i*f[i-1]       #the recursion + adding in the list#
        return f[n]

Now How do i use a decorator to make this work? Following is my attempt ''' #tabulation (down to up) with decorator

import time

def tabulation(func):
    def inner(*args,**kwargs):
        n=str(args)+str(kwargs)
        n=int(n[1])
        m=[0]*(n+1)
        if n not in m:
            m[n]=func(*args,**kwargs)
        print(m)
        return(m[n])
    return inner


@tabulation
def fact(n):
    if n<=1:
        return n
    else:
        return n*fact(n-1)

start=time.time()
f=fact(5)
end=time.time()
start=time.time()
g=fact(10)
end=time.time()
print(f," ",end-start)
print(g," ",end-start)
print(m)

'''

Answer 1

The table should be defined ouside the inner function so that it can be shared across calls. However, with the table defined outside the inner function, it can't be initialized with any items since n is not known until the inner function is called. Instead, grow the table dynamically with the list.extend method as needed:

def tabulation(func):
    def inner(n):
        table.extend(map(func, range(len(table), n + 1)))
        return table[n]

    table = []
    return inner

@tabulation
def fact(n):
    if n < 1:
        return 1
    return n * fact(n - 1)

so that:

import time

start = time.perf_counter()
f = fact(5)
end = time.perf_counter()
print(f, " ", end - start)
start = time.perf_counter()
g = fact(10)
end = time.perf_counter()
print(g, " ", end - start)

outputs:

120   8.546994649805129e-06
3628800   3.326000296510756e-06

Demo: Try it online!