算法策略

最长公共子序列问题  最长公共子序列(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数，其以比利时数学家欧仁·查理·卡塔兰… 阅读全文