*【例5】装配线调度问题4.构造问题的最优解用li[j]表示装配线号其值为1或2，表示最快通过Sij的站点j-1所在的装配线。这里j=2,3,4,…n。用L*表示最快通过站点n所在的装配线。Output-station(L,i,j)ifj=0thenreturnOutput-station(L,li[j-1],j-1)print“line”i“,station”j*【作业】3.A=“xzyzzyx”Y＝“zxyyzxz”用动态规划法求解LCS。4.已知装配线调度问题的各参数如下表所示，请给出该问题的解。j1234567b1j7934845t1j231342t2j212213b2j8564576i12ei23oi32【作业3答案之一】YA01x2z3y4z5z6y7x0000000001z0←0↖1←1↖1↖1←1←12x0↖1←1←1←1←1←1↖23y0↑1←1↖2←2←2↖2←24y0↑1←1↖2←2←2↖3←35z0↑1↖2←2↖3↖3←3←36x0↖1←1↑2↑3←3←3↖47z0↑1↖2←2↖3↖4←4←4*3.8最优二分检索树（BST）【例6】给定n个关键字组成的有序序列S=s1,s2,…sn,利用这些关键字建立一棵二分检索树。其中，每个关键字si存在相应的检索概率为pi，另设n+1个虚拟外部结点e0(所有小于s1的值)，e1,…en(所有大于sn的值),表示不在S中的那些值，每个外部结点的检索概率是qi。对于给定的概率集合，我们想要构造一棵具有最小期望检索开销的二分检索树，并称之为最优二分检索树。最小期望开销即能够使得在所有查找中所访问的结点总数达到最小。*查找成功与不成功的概率二分检索树的期望开销有个节点的二叉树的个数为：穷举搜索法的时间复杂度为指数级二分检索树的期望开销*二分检索树的期望开销示例*【练习】已知A1 A2 A3 A43×5 5×4 4×2 2×6给出以上4个矩阵连乘时的最少乘数次数，并由此给出计算时的加括号方式。【最大子段和问题】给定由n个整数（可能为负整数）组成的序列a1,a2,…,an,求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：例如,当（a1,a2,a3,a4,a5,a6)=（-2,11,-4,13,-5,-2）时，最大子段和为:=20。最大子段和问题的动态规划算法（1）分析问题最优解的结构在问题的描述分析中我们注意到，若记b[j]=,1≤j≤n,则所求最大子段和为：由b[j]的定义易知，当b[j-1]0时，b[j]=b[j-1]+a[j]，否则，b[j]=a[j]。（2）建立递归方程b[j]=max{b[j-1]+a[j],a[j]},1≤j≤n最大子段和问题的动态规划算法----例：a[n+1]11-2-2-4-5130154326b[n+1]0015432601ij0sumbestibestj00jjjjjjjjjjjj-2121121122374201320245156求a=（-2，11，-4，13，-5，-2）的最大子段和。a[n+1]11-2-2-4-5130154326b[n+1]00154326jjjjjjjjjjjj-2117201315（3）计算最优值据此，可设计出求最大子段和的动态规划算法如下：intMaxSum（intn,int*a）{intsum=0,b=0,i=0,besti=0,bestj=0;for(intj=1;j=n;j++) {if(b0)b+=a[j]; else{b=a[j];i