Hints — p75 Palindrome Partitioning II

Hint 1. Two-phase DP. Don’t try to check palindromes inside the cuts loop — that’s O(n³). First precompute an is_pal[i][j] table, then run a separate cuts DP that consults it in O(1).

Hint 2. Phase 1 — fill is_pal[i][j] by increasing length. For length 1: True. Length 2: s[i]==s[j]. Length ≥ 3: s[i]==s[j] AND is_pal[i+1][j-1]. Fill order matters so the inner reference is already computed.

Hint 3. Phase 2 — cuts[i] = min cuts for s[:i+1]. If is_pal[0][i] then cuts[i] = 0. Else: cuts[i] = min(cuts[j-1] + 1) over every j such that is_pal[j][i] (every palindrome suffix ending at i).

Hint 4. Cuts vs partitions — off by one. K palindromic pieces need K-1 cuts. The DP returns cuts, not pieces.

Hint 5. Space optimization — expand-around-center alternative: instead of building the is_pal table, expand from each center (odd and even); when you discover s[l..r] is a palindrome, update cuts[r+1] = min(cuts[r+1], cuts[l] + 1). Same O(n²) time, only O(n) memory.

If stuck: see solution.py.