428. 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.

Constraints - `1 ≤ length ≤ 1000` - The string is lowercase English letters.