```
class Solution:
def checkValidString(self, s):
dp = [[-1]*(len(s)+1) for _ in range(len(s))]
def dfs(i,sm):
if i==len(s):
return sm==0
if dp[i][sm]!=-1: return dp[i][sm]
if sm<0: return False
if s[i]=='(': t1 = dfs(i+1,sm+1)
elif s[i]==')': t1 = dfs(i+1,sm-1)
elif s[i]=='*': t1 = dfs(i+1,sm) or dfs(i+1,sm+1) or dfs(i+1,sm-1)
dp[i][sm] = t1
return t1
return dfs(0,0)
```

Intuition: For each * encountered we can try all the three possibilities i.e. take it as a '(' (sm+1), ')' (sm-1), ''(sm).

There could be overlapping subproblems with respect to the the index i of the string with the sm encountered at that index. So just memorize the values for each i,sm encountered.

**sm** variable stores the cumulative sum i.e +1 for '(',

-1 for ')' and 0,+1,-1 for '*'.

**Base Case:**

- If at any point of time
**sm**<0 we know its useless to proceed so return False. - When we covered the entire string, return True if
**sm**==0.