Fewest Palindrome Cuts — Solution & Editorial

Back to the Problem

Precompute palindrome[i][j] by interval DP, then dp[i] = min cuts for the prefix of length i, extending from any j where s[j..i−1] is a palindrome.

Complexity: O(|S|²)