我一直在尝试完成大学的动态规划作业,但迄今为止没有成功。
问题:
给定一个 DNA 字符串和一个突变位置列表(例如,0 和 2 是突变),找到包含最多突变的最长回文子序列。
输入:一个长度为 0 到 2000 的字符串 S;一个整数 N,使得 0<=N<=|S|,以及 N 个突变位置(数字从 0 到 |S|)。
输出:表示包含最大数量的突变的最长回文子序列的大小的整数。
示例:
输入:CAGACAT 0
输出:5
输入:GATTACA 1 0
输出:1
输入:GATTACA 3 0 4 5
输出:3
输入:TATACTATA 2 4 8
输出:7
我们必须使用 C 代码编写它,但我真正需要的是想法,任何语言或伪代码对我来说都可以。
我的查找 LPS 的代码(使用 C 语言):
int find_lps(char *input)
{
int len = strlen(input), i, cur_len;
int c[len][len];
for (i = 0; i < len; i++)
c[i][i] = 1;
for (cur_len = 1; cur_len < len; cur_len++) {
for (i = 0; i < len - cur_len; i++) {
int j = i + cur_len;
if (input[i] == input[j]) {
c[i][j] = c[i + 1][j - 1] + 2;
} else {
c[i][j] = max(c[i + 1][j], c[i][j - 1]);
}
}
}
return c[0][len - 1];
}
我尝试对变异做的事情:
1- 创建一个改变LPS的位置数组。这不起作用,而且实际上,我不知道该怎么做。
关于问题的更多细节: 在有n个回文子序列的情况下,它们都具有相同的变异大小,我需要最长的子序列。考虑到您没有具有M次变异的回文子序列,如果您使用X次变异拥有n个回文子序列(我们有M次变异),则需要X次变异的最长回文子序列。如果有,则应选择其他子序列,即使它更短。所以,第一标准:在回文子序列中具有最多的突变。如果数量相同,则选择最长的子序列。
任何帮助都将不胜感激,谢谢。