Getting TLE for this problem

#1

My code-

#2

Calculate and maintain 2 DP states:

  1. pal[i][j] , which is whether s[i…j] forms a pal
  2. d[i], which
    is the minCut for s[i…n-1]

Once we comes to a pal[i][j]==true:

  • if j==n-1, the string s[i…n-1] is a Pal, minCut is 0, d[i]=0;
  • else: the current cut num (first cut s[i…j] and then cut the rest
    s[j+1…n-1]) is 1+d[j+1], compare it to the exisiting minCut num
    d[i], repalce if smaller.

d[0] is the answer.

see this

#3

Okay can you also tell me what is the difference in time complexity between my code and this code ?