算法策略

最长公共子序列问题  最长公共子序列(LCS)问题中LCS的定义为“对于任意两个序列$X,Y$，若$Z$为其LCS，则$Z$中的所有元素必然同时存在于$X,Y$中，且其在$X,Y$中的下标是递增的”。首先定义状态转移函数$F(i,j)$表示原问题中$X[0…i],Y[0…j]$子序列的LCS长度，容易得出状态转移方程如上，因为$F(i,j)$是单调递增的。如上图所示，在递推$F(i,j)$状态的同时，如果维护一个“备忘录”数组，则可利用其求出其中一个LCS，并且注意到对$F(i-1,j)=F(i,j-1)$的情况加以处理可求出全部LCS。下文的代码仅通过回溯状态转移数组求出其中一个LCS。 Python def dp(X,Y):… 阅读全文

最长LIS问题($O(n^2)$)最长LIS(上升子序列)问题是一个经典的动态规划问题，问题描述如下“LIS是指从左到右的排序子序列，对于任意给定序列$L$求出它所有上升子序列(LIS)的最大长度。例如$[1,3,9,6,8]$的一个最长LIS是$[1,3,6,8]$，其长度为4”。这个问题的朴素算法可以是先求出原序列的全部子集(保持原有顺序)，然后遍历判断其是否为LIS并记录长度。用$F(k)$表示“以$L[k]$结尾的最长LIS长度”。对满足$F(k)$的所有序列，若删去$L[k]$必是满足$\{F(i) | i\in [0,k-1]\}$中某问题的序列或空序列，且删去$L[k]$后的序列长度等于满足$L[i]<L[k]$的上述所有$F(i)$中的最大值。所以$F(k)$满足状态转移方程\(F(k)… 阅读全文

矩阵连乘的最优结合 1) 结合策略：矩阵乘法满足交换律，故通常无需加括号，有$a\times b$矩阵$X$，$b\times c$矩阵$Y$，$c\times d$矩阵$Z$，朴素乘法用结合策略$(XY)Z$的代价为$O(abc+acd)$，利用$X(YZ)$的代价为$O(bcd + abd)$，不同结合策略会导致不同的代价。规定待连乘的矩阵序列(下标)为$[A_1,A_2,…,A_n]$，维度序列为$[p_0,p_1,…,p_n]$，即$A_i$为$p_{i-1} \times p_i$矩阵； 2) 枚举法：设$P(n)$为$n$个矩阵连乘的结合(加括号)方案总数，则有$P(n)=\sum_{k=1}^{n-1} P(k)P(n-k)$，$P(1)=1$。解得\(P(n)=\Omega… 阅读全文

给定关键字的BST数目设$L$为包含$n$个关键字的元素互异的递增序列，把$L$可形成的所有形态的BST数目计为$C(n)$，然后推导$C(n)$的递推表达式，其核心在于按$L$每个元素作树根的情况划分问题，然后得出$C(n)$与每个根节点左右子树的$C$的关系并求和：第1个关键字为树根时有$C(n-1)$种情况，第2个关键字为树根时有$C(n-2)$种情况…第5个时有$C(4)C(n-5)$种…第k个时有$C(k-1)C(n-k)$种…。整理得到$C(0) = 1$，$C(n+1) = \sum_{i=0}^n C(i)C(n-i)$。$C(n)$被称为Catalan数，其以比利时数学家欧仁·查理·卡塔兰… 阅读全文