作者makiyolove (暴力熊)
看板Programming
标题[问题] dna序列密度
时间Mon May 18 11:20:58 2009
在网路上看到的题目
DNA序列是由A、T、C、G组成一串字串序列
举例:agGCTGCAatGACAGTTGGG
然後找出大於使用者输入长度L
包含C、G密度最高的序列串
此题解应输出gGCTGC (假设L=5)
我只有想到用暴力法
列出每一种组合 计算密度 比较大小 再输出
应该有更快的方法可以用?
恳请板友指教
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 192.192.199.49
1F：推 march20:DP 66.75.255.220 05/18 15:35
2F：推 march20:先求出 A1~Ai 的CG 个数合, 然後对所有 66.75.255.220 05/18 15:38
3F：推 march20:max (S_i - S_(i-L+1)) for L<i<n 66.75.255.220 05/18 15:40
4F：推 march20:啊, 直接回文 66.75.255.220 05/18 15:46
5F：推 wa120:李家同Algorithms的书 多的是这种解题～ 140.133.13.134 05/18 18:32
6F：→ wa120:没记错的话是LCS problem 140.133.13.134 05/18 18:32
7F：推 sorryChen:对阿 不是赵老师和吕学一老师论文吗 128.125.87.33 05/19 11:34