The Printer That Prints Runs
A printer can only do one thing per turn: choose a character and a CONTIGUOUS range, and print that character across the whole range, overwriting whatever was there.
Starting from a blank strip, print the given string in the fewest turns.
aaabbb -> 2 print aaaaaa, then bbb over the right half
aba -> 2 print aaa, then b in the middle
abab -> 3
## Collapse the runs first
Two adjacent equal characters can always be printed by the same stroke, so a run of k
identical characters costs exactly what a single one of them costs.
Replacing every maximal run by one character therefore changes nothing about the answer, and
it shrinks the input. aaabbb becomes ab, which answers 2, and aaa becomes a, which
answers 1.
That step is not merely an optimisation: without it the recurrence below still works, but the reasoning about "the same character appearing again later" becomes cluttered by neighbours that were never distinct.
## The key observation
Consider the first character of a range. Its stroke has to happen at some point, and it can be EXTENDED to cover any later occurrence of the same character, at no extra cost.
So either that stroke covers only position i, or it is shared with some later position
k holding the same character.
dp[i][j] = 1 + dp[i+1][j] its own stroke
dp[i][j] = min over k in (i, j] with t[k] == t[i] of
dp[i+1][k-1] + dp[k][j] share the stroke with k
## Why sharing costs nothing extra
If the stroke that prints position i is stretched to reach k, everything strictly
between them gets overwritten afterwards by the strokes counted in dp[i+1][k-1].
So the shared stroke is already paid for inside dp[k][j], and the two pieces add without
a plus one. That missing plus one is the whole saving, and writing it as
1 + dp[i+1][k-1] + dp[k][j] gives an answer that is too large on every string with a
repeat.
aba answers 2 and is the smallest case that shows it: a solution charging for both a
strokes answers 3.
## Fill by length, as always
dp[i][j] reads dp[i+1][j], dp[i+1][k-1] and dp[k][j], all shorter ranges.
## Boundaries
A single character answers 1. abc answers 3, since no character repeats and nothing can be
shared.
aabbaa collapses to aba and answers 2, which is the check that collapsing and the
sharing rule work together.
abcba answers 3: print aaaaa, then bbb in the middle, then c. The two as share
and the two bs share.
## Cost
Time O(n^3) after collapsing. Space O(n^2).