I am getting the error in the following code for the above stated problem using memoization please help me find the error and correct the code.
import sys #sys.setrecursionlimit(10**5) import math cache={} def m(n): if n==0: return 0 ans=sys.maxsize root=int(math.sqrt(n)) for i in range(1,root+1): nc=n-(i**2) if cache[nc] not in cache: sa=m(nc) cache[nc]=sa curr=1+sa else: curr=1+cache[nc] ans=min(ans,curr) return ans print(m(int(input())))
Advertisement
Answer
It would help if you provided the full error output, which should include the line number and surrounding code. However, I suspect the issue lies in the following line:
if cache[nc] not in cache:
You’re checking whether the value of a dictionary key exists as a dictionary key. I assume you actually meant this (which will check whether a value is an existing dictionary key):
if nc not in cache: