I came across this problem through commonlounge and I thought it was a textbook DP problem and many people seem to have done it that way. However, only 3 test cases passed for me and the rest are showing TLE even though I have memoized the solution. Please help me understand why the time limit is being excited and any feedback will be greatly appretiated!
Here is my code:
(CodeChef: Practical coding for everyone)
import sys
n = int(input())
arr = list(map(int,input().split()))
memo = [None for i in range (n)]
memo[-1]=0
memo[-2]=0
memo[-3]=min(arr[-3:])
i = 0
def supw(arr,x):
if memo[x]!=None:
return memo[x]
else:
print(x)
memo[x]= min(arr[2]+supw(arr[3:],x+3),arr[1]+supw(arr[2:],x+2),arr[0]+supw(arr[1:],x+1))
print(memo[x])
return memo[x]
sys.setrecursionlimit(10**6)
print(supw(arr,i))
print(memo)