Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.
I tried to start by coming up with the base cases, subproblem and recurrence but having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)
[A, B, A, G, C, C, G, T, O, O, T ] is made up from 3 subsequences, namely
[A, B, A] + [G, C, C, G] + [T, O, O, T]
So, therefore, my output for this example would be
Thanks in advance!