Palindrome Partitioning II
Combine a precomputed palindrome table with 1D DP to find the minimum cuts needed to partition a string into palindromes.
Problem: Minimum Cuts to Partition
Palindrome Partitioning II asks: given string s, find the minimum number of cuts so that every substring in the partition is a palindrome. For 'aab', one cut gives ['aa', 'b'], so the answer is 1. For 'a' the answer is 0 (already a palindrome). This problem combines two DP phases: first precompute which substrings are palindromes, then use 1D DP to find minimum cuts.
Phase 1: Precompute Palindrome Table
First build is_pal[i][j] = True if s[i..j] is a palindrome using interval DP. This runs in O(n²) time and O(n²) space. Alternatively, expand-around-centre fills the same table in O(n²) time. We need this table because the 1D cut DP will query is_pal[i][j] repeatedly — precomputing avoids recomputing palindrome checks inside the cut DP loop.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))