3、。显然时间复杂度为O(n2)。上述式子的含义：找到i之前的某j，这个数不比第i个数小,对于所有的j取f(j)的最大值。问题2：乘积最大设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：有一个数字串：312，当N=3，K=1时会有两种分法：⑴3*12=36⑵31*2=62这时，符合题目要求的结果是：31*2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。分析假设s1‥si(2≤i≤n)中
4、插入j个‘*’。其中s1‥sk中插入了j-1个‘*’，即乘式中的第j+1项为sk+1‥si(j≤k≤i-1):设ans[i,j]—长度为i的数串中插入j个‘*’的最大乘积（整型数组）。显然，ans[i,0]=si…s1对应的整型数组；ans[i,j]=max{ans[k,j-1]*sk+1‥si}（1≤i≤n,1≤j≤min{i-1,m}）问题3:求最长公共子序列给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得
5、对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。给出两个字串S1和S2，长度不超过5000.求这两个串的最长公共子串长度。分析样例S1=“ABCBDAB.”S2=“BABCBD.”可以看出他们的最长公共子串有ABCB,ABCD,BCBD等，长度为4.从样例分析，我们思考的方式为要找出S1串与S2串的公共子串，假设将S1固定，从第1个位置开始直到最后一个位置为止，与S2的各个部分不断找最长公共子串当然S1也可以变化，这样我们即得出了思路:枚举S1的位置i枚举S
6、2的位置j找出S1的前i位与S2的前j位的最长公共子串，直到两个串的最后一个位置为止。动态规划设f(i,j)表示S的前i位与T的前j位的最长公共子串长度。则有，时间复杂度O(n*m)主程序框架n:=length(a);m:=length(b);fori:=1tonbeginforj:=1tomdobeginf[j]:=max(f[j-1],pf[j]);{从前面的状态直接转移过来}if(a[i]=b[j])and(pf[j-1]+1>f[j])then{多增加一位的情况}f[j]:=pf[j-1]+1;end;pf:=f
7、;end;说明：pf是一个与f完全相同的数组，实现f(i)与f(i-1)的滚动样例运行过程S=“ABCBDAB.”T=“BABCBD.”初始：f(i,0)=0,f(0,i)=0;∵S[1]≠T[1];∴f(1,1)=MAX{f(1,0),f(0,1)}=0∵S[1]=T[2];∴f(1,2)=MAX{f(1,0)+1}=1∵S[2]=T[1];∴f(2,1)=MAX{f(1,0)+1}=1∵S[2]≠T[2];∴f(2,2)=MAX{f(1,2),f(2,1)}=1∵S[2]=T[3];∴f(2,3)=MAX{f(1,2
8、)+1}=2∵S[3]≠T[1];∴f(3,1)=MAX{f(3,0),f(2,1)}=1∵S[3]≠T[2];∴f(3,2)=MAX{f(2,2),f(3,1)}=1∵S[3]≠T[3];∴f(3,3)=MAX{f(3,2),f(2,3)}=2……一直求到f(8,7),ans=f(8,7)-1；减1是因为最后都有一
