如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。

来自"NOCOW"

以下内容的版权由Ceeji所有。版权所有者不允许别人随意修改这些内容。请不要编辑这些内容（原作者的版本更新除外）。 如果你愿意重写这部分内容并以GNU FDL协议发布，请把这些内容移动到Article:名字空间或者直接删除并把原文链接加入本条目的讨论页。 NOCOW在这里使用这些内容是因为目前还没有允许任何人编辑的替代版本。请不要在有足够多内容的位置加入非自由版权的内容。

本解题报告由 Ceeji 编著，转载请注明出处。

　　这道题是典型的双重动态规划。 　　第一步：由题意可以知道，分化具有阶段性和规律性，这正是动态规划的特征。由于要求的是最少的特等基因数目，所以考虑一次分化的情况。要一次分化到的串设为T，假设字符Ch1能够一次分化成Ch2和Ch3，并且Ch2能够一次分化成从第p位到第i位的字符串，而Ch3能够一次分化成从第i+1位到第q位的字符串，那么必有Ch1能够一次分化到从第p位到第q位的字符串。如Ch1=S,Ch2=A,Ch3=B时，S->AB，A->BC，B-> CD，则 S -> BCCD。需要穷举 Ch2 和 Ch3，所以使用了数组模拟链表。动态转移方程如下：

can[ch1,p,q]:= can[ch2,p,i] and can[ch3,i+1,j] 

can[ch1,p,q]:= can[ch2,p,i] and can[ch3,i+1,j] 其中ch1能够一次分化到ch2和ch3。这里的i作为划分点，再次体现了二分的思想。 　　由于本人的程序中使用了记忆化搜索的思想，所以 can 设置为了数值型，初始值为 0，能够一次分化为 1，否则为 2。 　　第二步：由上面的思路可以得出任意一个字符Ch能否一步分化到字串T的任意一段。那么，如何得出指定字串至少由S多少次分化可以得到呢？可以再次使用动态规划思想。假设DP[i]表示T的前i位字串至少需要的特等基因的数目，那么易得动态转移方程如下：

DP[i]:= min {DP[j] + 1}; 

DP[i]:= min {DP[j] + 1}; 其中的 j 符合

can['S',j+1,i]=true 

can['S',j+1,i]=true 　（或，记忆化搜索中使用 can['S',j+1,i]=1 can['S',j+1,i]=1）