Hints — p77 Strange Printer

Hint 1. Greedy (“paint biggest run first”) fails on “aba”. You need DP. What’s the state? Try interval DP: dp[i][j] = min turns to print s[i..j].

Hint 2. Base: dp[i][i] = 1. For the general case, start with the naive: dp[i][j] = dp[i+1][j] + 1 (one stroke for s[i] alone, then print the rest).

Hint 3. Key insight: if s[k] == s[i] for some k in (i, j], the stroke painting position i can EXTEND to cover position k in the same turn. So dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) — the +1 for position k is absorbed.

Hint 4. Fill order: length-major. Outer = interval length 1..n; inner = i with j = i + length - 1. Ensures dp[i+1][j], dp[i+1][k-1], dp[k][j] are all already computed.

Hint 5. Preprocess: collapse consecutive duplicates (“aaabbb” → “ab”). Doesn’t change the answer (one stroke handles a run of duplicates) and shrinks the DP table.

If stuck: see solution.py.