Partitioning DP on Intervals and Segments

Partition DP splits sequences into segments with a cost per segment—palindrome partitioning, burst balloons style interval DP dp[i][j].

Why this shows up in the real world

Text line breaking minimizes badness per line. DNA segment labeling.

Core idea (explained for students)

Try all split points k between i..j-1: dp[i][j]=min_k cost(i,k)+dp[k+1][j].

Try this in Python

def min_cut_palindrome(s: str) -> int:
    n = len(s)
    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 = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        dp[i] = n - i
        for j in range(i, n):
            if is_pal[i][j]:
                dp[i] = min(dp[i], 1 + dp[j + 1])
    return dp[0] - 1


print(min_cut_palindrome('aab'))

Common mistakes

• O(n^3) too slow for large n without pruning.
• Off-by-one on inclusive ranges.

Key takeaways

• Prefix preprocessing (is palindrome[i:j]) turns inner checks O(1).