a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=
i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
iii. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=
最长公共子序列问题具有最优子结构性质。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024