The following question is taken from leetcode: 1278. Palindrome Partitioning III
You are given a string $s$ containing lowercase letters and an integer $k$. You need to:
- First, change some characters of $s$ to other lowercase English letters.
- Then, divide $s$ into $k$ non-empty disjoint substrings such that each substring is a palindrome.
Return the minimal number of characters that you need to change to divide the string.
So I did find the cost array to make a string to a palindrome. Something like below:
[('bcccdefg', 4), ('ccde', 2), ('ccdef', 2), ('ef', 1)] # (character, cost to make it a palindrome)
I am thinking whether this can be done using knapsack recurrence relations, where profit will be cost and weight will be length of the substring; the total backpack weight will be the length of the main string. Though I am not sure what to do with $k$. Do I need 3 states, or are 2 states enough?
Is my thinking correct? If no, what is the right way to write a recurrence relation for this?