去年算法作业答案-第三章分析题3-1设计一个On2时间找出由个数组成

第三章动态规划算法分析题3-1 设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列(LongestIncreasingSubsequence)分析示当以a[i]为单调递增子序列最后一个元素时，所得最长单调递增子序列的长b[i] i0k0kintLIS(vector<int>a,vector<int>b{

a[k]inti,for(i=0;i<n;++i{b[i]=for(j=0;j<i;++j{if(a[j]<a[i]&&b[j]+1>b[i])b[i]=b[j]+1;}} maxinumb //b数组的最大值即aLIS}n），该解法的时间复杂度为O(n2)。算法分析题3-2 将3.1中算法的计算时间缩减至O(nlogn)(提示：分析Li表示。易知：L1<=L2<=…<=Lm如果Li>Lj(i<j)，那么去掉以Lj结尾的递增子序列的最后j-i个元素，得到一iak<=Lj<LiLii的递aLLiLm，那么m就是最大单调子列的长度。用下面的方法可以用来L。ai<L1杂度为logn，于是总的复杂度为O(nlogn)。算法实现题3-1独立任务最优调度问2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机iaibij，aj<bj。22个作业。设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一太机器停工的总时间。研究(a1,a2,a3,a4,a5,a6)=(b1,b2,b3,b4,b5,b6)=分析T[i][kkAi时，B处理器所花费的最小时间。例如，当A处理机花费时间等于0，即A没有参与k就是k个任务的时间和，则：kT[0][k]T[i][k]min(T[ia[k]][k1],T[i][k1]KA处理机来做，B处理机不费的最小时间。假如将第K个任务交给B处理机来做，A处理机不动，这样完KK-1个任务，A处理机花费时间小i时，BKB处理机上花费的时，即算法实现3-5乘法表问定义与字母表{a,bc分析

依此乘法表，对任一定义于上的字符串，适当的加括号后得到一个表达式。例如，对于字符串x=bbbba，它的一个加括号表达式为(b(bb))(ba)。依乘法表，该表达式的值为a。试设计一个动态规划算加括号方式，使由x导出的加括号表达式的值为a。abcabbabcbacaccf[i][j][0]：字符串中第i个元素到第j个元素的子串表达式值为a的加括号方式数f[i][j][1]：字符串中第i个元素到第j个元素的子串表达式值为b的加括号方式数f[i][j][2]：字符串中第i个元素到第j个元素的子串表达式值为c的加括号方式数jfij0fik0*fik12fik1*fik12fik2*aik结果保存于f[0][n-1][0]算法实现题3-2编辑距离问(1)删除一个字符(2)一个字符(3)d(A,B)。试设计一个有效算法,2AB,计算出它们的编辑距离d(A,B)。分析设字符串 Bj的最短编辑距离，其中 Bj=b1,b2…bjai=bj，d[i][j]d[i1][jd[i][j]d[i1][j1]d[i][j]d[i1][j]d[i][j]d[i][j1]d[0