Recursion & DP Target: 15s
Two-phase DP: first build O(n²) palindrome lookup, then find min cuts. Common two-table pattern.
def minCut(s):
n = len(s)
# precompute palindrome table
is_pal = [[False]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or is_pal[i+1][j-1]):
is_pal[i][j] = True
# dp[i] = min cuts for s[0..i]
dp = list(range(n)) # worst case: cut before every char
for i in range(1, n):
if is_pal[0][i]:
dp[i] = 0; continue
for j in range(1, i+1):
if is_pal[j][i]:
dp[i] = min(dp[i], dp[j-1] + 1)
return dp[n-1]Type it from memory. Go.