Can you reduce this problem to a classic problem?

The problem is equivalent to finding any palindromic subsequence of length at least N-K where N is the length of the string.

Try to find the longest palindromic subsequence.

Use DP to do that.