步骤1~3是动态规划算法的基本步骤。
在只需要求出最优值的情形,步骤4可以省略;
若需要求出问题的一个最优解,则必须执行步骤4。...设A是p×q的矩阵, B是q×r的矩阵, 乘积是p×r的矩阵;计算量是pqr。...4.3 最长公共子序列
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:...4.3.1 最长公共子序列的结构
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则
若xm=yn,则zk=xm=yn,且zk-1是xm...若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。
若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。