Palindrome Partition Theory

1. Preprocessing

Fill palindrome table by length; each check O(1) using inner substring.

for len in 1..n:
  for i in 0..n-len:
    j = i+len-1
    if s[i]==s[j] and (len<=2 or pal[i+1][j-1]):
      pal[i][j] = True

2. Recurrence

if pal[0][i]:
  dp[i] = 0
else:
  dp[i] = min(dp[j] + 1) for 0<=j<i if pal[j+1][i]

3. Complexity

• O(n²) time / space with table (vs O(n³) naive).
• Space can be reduced using center expansion but code complexity rises.

4. Notes & Variants

• Return partitions: track predecessor j giving best cut.
• All partitions: backtrack exploring pal substrings (exponential enumeration).
• Manacher can precompute palindrome radii in O(n) for optimization tasks.