Partition DP — Palindrome Partitioning II

Partition DP Pattern

The idea: try every possible partition point and take the optimal one. dp[i] = min cuts to partition s[0..i] into palindromes. For each i, check all j where s[j..i] is a palindrome.

Recurrence

dp[i] = 0 if s[0..i] is palindrome
else:
  for j = 1 to i:
    if s[j..i] is palindrome:
      dp[i] = min(dp[i], dp[j-1] + 1)

Interactive Visualization

Computing dp[i]

Palindrome Range

Answer

String:

String

dp[i] = min cuts for s[0..i]

Step 0 of 0

Computing

—

Trying Cut at

—

dp[i]

—

Min Cuts

—

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — Palindrome Partitioning II

int minCut(string s) {
    int n = s.size();
    vector<int> dp(n, 0);
    vector<vector<bool>> pal(n, vector<bool>(n, false));

    // Precompute palindrome table
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            pal[i][j] = s[i]==s[j] && (j-i<2 || pal[i+1][j-1]);

    for (int i = 0; i < n; i++) {
        if (pal[0][i]) { dp[i] = 0; continue; }
        dp[i] = i; // worst: cut every char
        for (int j = 1; j <= i; j++)
            if (pal[j][i])
                dp[i] = min(dp[i], dp[j-1] + 1);
    }
    return dp[n-1];
}

Complexity

Time

O(N²)

Precompute palindromes + DP fill.

Space

O(N²)

Palindrome table + DP array.

📝 Notes

▼