Splitting Into k Palindromes
Split the string into exactly k non-empty consecutive pieces. Each piece must be made
into a palindrome by CHANGING characters, one change per character. Print the fewest changes
in total.
abc, k = 2 -> 1 a | bc, changing one of b or c
aabbc, k = 3 -> 0 aa | bb | c, all already palindromes
## Two tables, each simple
cost[i][j] = changes needed to make s[i..j] a palindrome
dp[i][g] = fewest changes for the first i characters split into g pieces
The interval table supplies the piece costs and the partition table consumes them. Neither half is hard; keeping them separate is what makes the whole thing manageable.
## The piece cost
Walking from both ends inward, each mismatched PAIR costs exactly one change, since changing either character fixes the pair:
cost = number of positions t with s[i+t] != s[j-t], over t < (j-i+1)/2
A middle character in an odd-length piece has no partner and costs nothing, which is why the loop stops when the two pointers meet.
Counting mismatched CHARACTERS rather than pairs doubles every cost. ab with k = 1
answers 1 and is the test: two characters mismatch, one change fixes them.
## The partition
dp[0][0] = 0
dp[i][g] = min over p of dp[p][g-1] + cost[p][i-1]
with p running from g-1 to i-1, so every piece is non-empty.
## The bounds on p
The first p characters must fill g-1 non-empty pieces, so p >= g-1. The last piece
must be non-empty, so p <= i-1.
Getting the lower bound wrong lets a piece be empty and the answer comes out too small. That
is the same bound as problem 561, and the same check applies: with k equal to the string
length, every piece is one character and the answer must be 0.
leetcode with k = 8 answers 0 and is that test.
## Two boundaries worth pairing
ab with k = 1 answers 1 and with k = 2 answers 0. Same string, and more pieces can
only help, because a single character is always a palindrome.
More generally the answer is non-increasing in k, which is a cheap sanity check on any
implementation.
## An input worth tracing
abcde with k = 2 answers 2. The splits are a|bcde costing 2, ab|cde costing 1 + 1,
abc|de costing 1 + 1, and abcd|e costing 2. Every split costs 2, so the answer does not
depend on the choice, which makes it a poor test of the split logic and a good test of the
cost function.
## Cost
Time O(n^2) to build the costs incrementally, or O(n^3) directly, plus O(n^2 k) for
the partition. Space O(n^2).