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.

## 10. Regular Expression Matching

# 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)