Everything is still a Palindrome

This problem has a $O(n ^ 2)$ dynamic programming (DP) solution ( $n$ as the string size). There are a few different implementations, the following one is one of them:

Consider that the string has size $n$ , the first position is indexed at $1$ and $s[i...j]$ is a substring of $s$ which starts at $i$ and ends at $j$ .

First, we have to check if the substring $s[i...j]$ is a palindrome for all $1 \leq i, j \leq n$ . It can be done using a simple DP: $s[i...j]$ is a palindrome if $s[i] = s[j]$ and $s[i+1...j-1]$ is a palindrome. If $i \geq j$ , we define that $s[i...j]$ is a palindrome. This preprocess method has $O(n^2)$ complexity. Note that checking if $s[i...j]$ is a palindrome in the naive way (using a for loop) has $O(n^3)$ complexity for all $1 \leq i, j \leq n$ .

Now, we make a second DP to solve the problem. Consider $dp[idx]$ the answer for the problem for the substring $s[1...idx]$ . Then for all $1 \leq i \leq idx$ , if $s[i...idx]$ is a palindrome, we can split the string into $s[1...i-1]$ and $s[i...idx]$ . Thus, the answer for $dp[idx]$ is the minimum of $dp[1...i-1] + 1$ for all $i$ such that $s[i...idx]$ is a palindrome. The answer for the problem is $dp[n]$ . This has $O(n^2)$ complexity, so the overall complexity is $O(n^2)$ , which is fast for $n = 1000$ . You can check my C++ implementation here .