Palindrome Partitioning DP

#User function Template for python3
#T.C:O(n**2)
#User function Template for python3
'''
Idea

Let isPalindrome(l, r) be True if string s[l...r] is palindrome else False.
Let dp(i) denote the minimum number of palindrome substrings of string s[i..n-1].
The answer is dp(0) - 1 which is number minimum cuts need to be made on string s[0..n-1].
Complexity

Time: O(N^2)
Time complexity for isPalindrome(l, r) is O(N^2)
Time complexity for dp(i) is O(N^2)
So total time complexity is O(N^2).
Space: O(N^2)

'''
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
class Solution:
    def palindromicPartition(self, s):
        @lru_cache()
        def palindrome(i,j):
            if i==j:return True
            if i+1==j:
                return s[i]==s[j]
            if s[i]==s[j]:
                return palindrome(i+1,j-1)
            return False
        n=len(s)
        @lru_cache()
        def dp(i):
            if i==n:return 0
            ans=float('inf')
            for k in range(i,n):
                if palindrome(i,k):
                    ans=min(ans,1+dp(k+1))
            return ans
        return dp(0)-1# we have to sub -1 because take e.g. 'aaa'. Reason at base case are also we are adding extra parition. That we have to remove

#T.C.:O(n**3)
class Solution:
    def palindromicPartition(self, s):
        n=len(s)
        dp=[[-1]*(1+n) for i in range(1+n)]
        bools=[[None]*(1+n) for i in range(1+n)]
        def ispalindrome(i,j):
            l,r=i,j
            if bools[i][j]!=None:return bools[i][j]
            while l<=r:
                if s[l]!=s[r]:
                    bools[i][j]=False
                    return False
                l,r=l+1,r-1
            bools[i][j]=True
            return True
        def find(i,j):
            if i>=j:return 0
            if dp[i][j]!=-1:return dp[i][j]
            ans=float('inf')
            if ispalindrome(i,j):return 0
            '''
            An Optimization: We will make the partition only if the string till the partition
        (till Kth position) is a valid palindrome. Because the question states that all
        partition must be a valid palindrome. If we dont check this, we will have to
        perform recursion on the left subproblem too (solve(str, i, k)) and we will waste
        a lot of time on subproblems that is not required. Without this the code will give
        correct answer but TLE on big test cases.
            '''
            for k in range(i,j):
                if ispalindrome(i,k):
                    ans=min(ans,1+find(k+1,j))
            dp[i][j]=ans
            return ans
        return find(0,n-1)