动态规划中的最长公共子序列学习教案

1、会计学1动态规划中的最长公共动态规划中的最长公共(gnggng)子序列子序列第一页，共16页。第1页/共15页第二页，共16页。n 不一定。如不一定。如A, B与与B, An 本节的问题是只找出一个最长公共本节的问题是只找出一个最长公共(gnggng)子序列。子序列。第2页/共15页第三页，共16页。第3页/共15页第四页，共16页。第4页/共15页第五页，共16页。第5页/共15页第六页，共16页。第6页/共15页第七页，共16页。可以。这样做不利于描述，如前面可以。这样做不利于描述，如前面Xm1可可以方便以方便(fngbin)地表示地表示X前前m 1 个元素个元素，改后就比较麻烦。从递归的

2、角度来看，改后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。一般也是从后面增减元素。第7页/共15页第八页，共16页。足子问题重叠性质。足子问题重叠性质。第8页/共15页第九页，共16页。第9页/共15页第十页，共16页。第10页/共15页第十一页，共16页。X = A C B D Y = A B D A c b00000011110111101222012330000001331022220213302213ijxi=yjci-1j=cij-111Y2N3N4Y21NY2NY第11页/共15页第十二页，共16页。n1. X=B, C, A, D Y=C, A, B, D,求X与Y的最

3、长公共(gnggng)子序列，并画出数组c与b.n c b00000000110111101222012230000002213013220213302221i:j:第12页/共15页第十三页，共16页。n1. X=B, C, A, D Y=C, A, B, D,求X与Y的最长公共(gnggng)子序列，并画出数组c与b.n c b00000000110111101222012230000002213013220213302221i: 1 2 3j: 1 2 3 4 1 2 3 4 1 2 3 4第13页/共15页第十四页，共16页。面向对象的局部来看是结构化的。面向对象的局部来看是结构化的。

4、结构化的基本思想是结构化的基本思想是“自顶向下，逐步求精自顶向下，逐步求精”,面向面向对象的基本意图是提高软件模块的复用性。对象的基本意图是提高软件模块的复用性。纯结构化的程序编译纯结构化的程序编译(biny)后基本上没有多余的代后基本上没有多余的代码，而面向对象的程序有许多。码，而面向对象的程序有许多。面向对象以机器的运行复杂度换取编程人员的编写面向对象以机器的运行复杂度换取编程人员的编写复杂度。复杂度。第14页/共15页第十五页，共16页。NoImage内容(nirng)总结会计学。定义：如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。第1页/共15页。对于任意给定的X和Y，它们的最长公共子序列唯一吗。第2页/共15页。设序列X=x1, x2,。, zk,则。第3页/共15页。第4页/共15页。讨论。因此(ync)