动态规划

动态规划 20世纪50年代初，美国数学家R.Bellman等在创立了动态规划(Dynamic Programming)，用于解决多阶段决策过程的问题。所以动态规划最早是应用数学、运筹学中的概念，并非算法概念。在用动态规划策略解决问题时，解题者需要先把问题拆分成有序的多个“阶段”，这些“阶段”的“形式”通常一样。后面的“阶段”的解可以根据前面若干个不同“阶段”的解来确定，但不能被更后面的“阶段”的解所决定(这也称为无后效性)。这种关系需要被描述成通常包含递推函数的“状态转移方程”。借助状态转移方程，就能依次得到每个“阶段”的解，最终得到问题的解。可以发现，“阶段”就类似分治法中的“子问题”，“状态转移方程”就类似解决“子问题”的递归程序，所以动态规划和分治法的策略框架基本一样，也可能分治法外延更广一点。… 阅读全文

(01)背包问题 之前讨论过该问题的一种分治算法，这里讨论一种更优的DP(动态规划)算法，其沿用之前的子问题划分思路，依赖数值的递推关系。先定义函数\(F(k,V)\)为“体积\(V\)的背包与物品前\(k+1\)项子序列\([t_0…t_k]\)能取到的最大总价值”。根据在分治法的讨论，可得\(F\)的递推式\(F(k,V) = max\{ F(k-1,V-A_k)+B_k, F(k-1,V) \} \)，该式也称为状态转移方程。需要注意其边界情况，\(V-A_k<0\)时说明物品本身的体积就超过背包容积，此时\(F(k,V)=F(k-1,V)\)。另一个边界情况是序号取-1时，显然有\(F(-1,V)=0\)。此时等于找到了最大总价值的递推关系，而不是解本身的递推关系。 然后是求\(F(k,V)\)，这里不用分治法“自顶向下递归”的方式，而是用“自底向上迭代”的方式。先初始化二维序列\(F[x][y]\)，然后从\(F[0][0]\)开始计算出每个下标对应的值，直到得出\(F[k][V]\)本身。这是DP中常用的计算方式，其相比函数递归，能避免对同一输入的多次计算，其缺点是需要建立维护数组，也会计算一部分之后用不上的值。… 阅读全文

二维(01)背包问题 其可描述为“设物品序列中每个物品只有1个，物品\(i\)有2个费用属性\(x_i,y_i\)，有1个价值属性\(w_i\)。给定2个正整数\(U,V\)，求物品组合使\(\sum x_k \leq U \)与\(\sum y_k \leq V \)时，\(\sum w_k\)最大”。形象一点来说就是背包除了体积限制，还有重量限制。 问题的状态转移方程是\(F(i,u,v) = max\{~ F(k-1,u-x_i,v-y_i)+w_i, F(k-1,u,v) ~ \} \)，参考(01)背包的思路很容易找到和证明该方程。问题的一个边界是\(u-x_i<0\)或\(v-y_i<0\)取\(F(i,u,v) = F(k-1,u,v) \)。下面给出用动态规划求解出\(F(i,u,v)\)的步骤，并且不讨论如何用求出来的\(F\)得到具体解。… 阅读全文

物品分组(01)背包问题 该问题是在(01)背包问题上附加条件“所有物品一开始被划入了几个不相交的物品组，且每组只能从中取其中一个”。这里不妨规定物品组也以序列给出，而每个物品组又都是1个物品序列。这里稍微改下\(F(k,V)\)的定义为“体积\(V\)的背包与物品组前\(k+1\)项子序列能取到的最大总价值”，即\(k\)是关于物品组的。 列出状态转移方程\(F(k,V) =max\{~F(k-1,V),~max\{ F(k-1, V-A_{k,i}) + B_{k,i} | i\in [0,|A_k|-1] \}~  \} \)，\(i\)是当前物品分组中的物品下标，\(A,B\)按二维数组(物品分组下标，物品下标)提供。得到方程的思路跟其他背包问题相似，这里略去讨论。要注意边界情况的处理，\(V-A_{k,i}<0\)时应直接剔除，不参与求\(max\)。这里同样略去通过\(F\)得到具体解的步骤。… 阅读全文

完全背包问题与多重背包问题 完全背包问题的描述是“给定容积为\(V\)的背包与物品序列，物品\(i\)的价值与体积分别为\(A_i,B_i\)。设序列中每个物品有无限个可以取，如何取物品可使总价值最大”。《算法导论》中的钢条切割问题就是完全背包问题。 这个问题本身可以转化成(01)背包问题，虽然每种物品有无限个，但背包容量却是有限的，故对于物品\(i\)，其至多能被取\(\lfloor{V/B_i}\rfloor\)次(其中\(\lfloor \rfloor\)表示向下取整，即直接丢弃小数点后的数)，从无限变为有限后就很好处理了，只需要把这些一样的物体“平铺”开就能得到一个新的物品序列，然后用这个新的物品序列求解对应的(01)背包问题即可。 按上述思路可得状态转移方程\(F(k,V)=max\{~ F(i-1,V-mB_i)… 阅读全文

最大连续子序列 之前讨论过该问题的一种分治算法，这里讨论基于另一种划分子问题策略的DP算法。设原数组\(L=[i_0,i_1,…,i_n]\)，函数\(F(k)\)为“\(L\)中以\(i_k\)结尾的全部连续子数组的元素值之和中的最大值”，则\(F(k)\)满足方程“\(F(k+1) = max\{ F(k) + L[k+1], L[k+1] \}\)，且\(F(0)=L[0]\)”。若解出\(F(0),F(1),..,F(n)\)，求出其中最大值即得原问题的解。该求解过程的编程实现通常是这样，先定义数组\(F[k]\)表示\(F(k)\)，从\(F[0]\)开始自低向高以数组递推并记录\(F[k]\)所有值，最后求数组\(F[k]\)的最大值即为解。算法代价为\(O(n)\)。 上述分析与解决问题的方法就是动态规划，其中关于\(F(k)\)的方程被称为动态规划的状态转移方程。该动态规划算法的代码既简短也易理解，但其实该问题本身并不特别简单，最大子数组问题最早于1977年提出，但直到1984年才被卡内基梅隆大学的教授Jay… 阅读全文

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