If this question appeared two years ago, it would probably end up being a hard question. Coming up with the O(NK) time DP solution is not something you can always expect.
Hi @whglamrock ,
Your point is absolutely right, I've changed the difficulty to "hard". : )
Have a nice weekend. : )