Range DP problems are problems that can use dp[i][j] to represent the states where i and j are the range in a list or array.

# Time complexity O(n) and the worst case is O(n^2)# space complexity O(n^2)
from functools import lru_cache
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@lru_cache(None)
def dp(i,j):
if j==len(p):return i==len(s)
firstmatch = len(s)>i and (p[j] in [s[i], '.'])
if j<=len(p)-2 and p[j+1]=='*':
#case 1 zero match
case1 = dp(i, j+2)
# case 2 many match
case2 = firstmatch and dp(i+1, j)
return case1 or case2
return firstmatch and dp(i+1, j+1)
return dp(0, 0)

Data Scientist/MLE/SWE @takemobi