Fewest Palindromic Pieces
Cut the string into pieces so that every piece reads the same forwards and backwards, and print the FEWEST pieces needed.
aab -> 2 aa | b
noonabbad -> 3 noon | abba | d
xyz -> 3 x | y | z
A single character is always a palindrome, so an answer always exists and never exceeds the length.
Problem #1151 prints EVERY palindromic cutting. That is an enumeration, and there can be exponentially many. This asks only for the size of the smallest, which is a table rather than a search, and the difference in cost is the point.
Two layers. First decide, for every pair (i, j), whether s[i..j] is a
palindrome:
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1])
filled with i descending so the inner range is already known. Testing each
substring by reversing it would make the whole solution O(n^3).
Then the cut count is a one-dimensional table over prefixes:
dp[0] = 0
dp[i] = 1 + min over j < i with pal[j][i-1] of dp[j]
Building the palindrome table first is what keeps the second loop cheap, and recognising that a shared sub-computation deserves its own pass is worth as much here as the recurrence.