动态规划

什么是动态规划

从度娘的这番话中我们不难理解，动态规划也是分为许多子问题，然后自下而上或者自上而下建立一个有规律的表达式即递归表达式进行推导复杂问题的最优解和最优解值。但是这里会打表暂存中途的计算结果以减少重复计算的次数提高性能(与dfs最大的不同)。

典型例题精讲

求解多段图的最短路径

对于上图的最短路径1->3->5->7，其子路径3->5->7是3->到目的节点7在图上的最短路径，所以可以总结出无论从1出发到[2,3,4]中的任意一个点，其后的路径也应为最短路径，即最优解的子集仍应该为子问题的最优解，并且前子问题对于后者最优解无影响，这是动态规划算法可以应用的根本前提。

所以借助上文我们可以列出递归表达式如下，设c(i)表示从i出发到目的节点7的最短路径，cost[i，j]为从i出发到j所用的权重，则有

$$c(1)=min\{c(k)+cost(1,k)\},k=2,3,4$$

并且我们易知c(7)=0；自此一个已知前提加上递归表达式可以自后向前推导出

0/1背包问题

解题思路

不选择贪心所用的密度值递减顺序放入物品，也不使用k-优化优化算法提高可信度的方法，而是选择直接用递归枚举求解物品放还是不放的方法。即无论优化解是否放物品1，相对剩余背包容量,优化解对物品2,…,n的放法, 也是优化解。

例如n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6]。其优化解为(1,1,0,0,1),即优化的物品装入背包的方法为物品1,2,5放入。物品1占背包容量2,剩下容量为8.优化解中包含的子问题转化为n=4,c’=c-2(物品1的重量),物品为2,3,4,5(1,0,0,1),即放物品2和5,是上述子问题的优化解，背包问题满足的优化原理。即每次我们都枚举物品是否放入来列递归式，设f(i,y)表示背包现有容量为y,放入物品i,…,n得到的优化效益值，则有：

$$f(i,y)=max\{f(i+1,y),f(i+1,y-wi)+pi\}$$

当然，上述式子成立的条件是物品i假设可以放入，然后在讨论是否放入的问题，如果无法放入则，就直接抛弃，式子改写为f(i+1,y)，所以可以列出0/1背包dp思路模板如下：

$$f(n,y)= \begin{cases} pn,y>=wn//可以放入第n见物品\\0,0<=y<wn//背包就放不下第n件物品 \end{cases}$$

上面的是前提已知条件，下面是递归模板

$$f(i,y)= \begin{cases} max\{f(i+1,y),f(i+1,y-wi)+pi\},y>=wi//能放入物品i\\ f(i+1,y),0<=y<wi//放不下物品i \end{cases}$$

根据上面的思路，我们可以写出c代码模板如下：

1
2
3
4
5
6
7
8
9
10

int F(int i,int y){
    //返回f(i,y)
    if(i==n){
        return (y<w[n])?0:p[n];
    }
    if(y<w[i]){
        return F(i+1,y);
    }
    return max(F(i+1,y),F(i+1,y-w[i]+p[i]));
}

下面我们就用上述思路来解题

递归实现

n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6]

首先我们先不想那么多，直接按照上面的递归表达式思路走一发。我们为了求解,调用F(1,10)求解f(1,10)。这里用递归树展开计算经过，其中每个节点用y值来标记，第j层的节点对应F(j,*)，因此根节点表示F(1,10),而它有左、右子节点,分别对应F(2,10)和F(2,8)。

上图中节点标出的是背包剩余容量，未标出的则为后面无法再放物品了，我们会发现本次运行执行了28次递归调用，并且灰色部分是重复进行了计算，这部分就和dfs递归调用等递归求解问题一样的共性缺点，重复计算消耗大量时间，为了减少没有必要的计算，我们可以暂存以前的计算结果，这样就只需要计算19次了，这也是dp算法总是要借助表格的原因。下面我们就介绍两种存储中途结果的方法。

w取整数时迭代实现

n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6]

当物品重量为整数时,可设计一相当简单的算法来求解f(1,y),这里我们使用二维数组f[i][y]存储每一个f(i,y)的值，并且计算一次，就长这个样子：

现在我们不用关心这个表的具体数值是怎么得到的，只要知道他长这个样子就可以了，所以这里是对每一个i都列举了y从0到10所有可能的情况下的最好取值。所以我们知道了二维数组需要n*c个空间大小。那么表中数字是怎么得到的呢，步骤如下：

首先我们先建立一个表，并初始化为0

然后我们还是需要先找到一个已知条件，这里不难看出就是f(5,y)为已知条件然后根据递归表达式自下而上推导，所以只要y<w5,f(5,y)就为0，当y>=w5时，f(5,y)为p5=6,因为w5=4,所以填入数据。变为：

然后推导f(4,y)=max{f(5,y),f(5,y-w4)+p4},所以当y>4时f(5,y)=6,f(5,y-w4)+p4=0,即虽然不能放物品4，但是已经可以放物品5了，所以y>4时至少f(4,y)至少为6，然后在看当y>=9时，此时f(5,y-w4)+p4=10，即4，5都可以放入背包，所以，此时表的值变为：

然后推导f(3,y),同理知道当y<4时，只能取f(4,y)的值，即和上一行的的取值相同，直到,y=6时，此时可以放入3,但是由于去最优化效益值，此时不放入3，即只放入4,5,效益值仍然是最大的，所以还是取f(4,y)的值，直到y取10，此时f(4,y-w3)+p3为11更大，所以效益值变为11，所以表的值变为：

然后推导2，与上面基本思路相同，所以最后表就变为了

可以看出来我们在给表赋值时用到了递归表达式，但是此时我们发现，和上面的裸递归方法不同，这里由于我们依次填表赋值并自上而下计算时，会用到上面的暂存结果的值，避免了重复计算的步骤，性能大大提升了，但是与次同时空间复杂性也提高了，并且我们还总结出来了中途接过存储数组的维度与条件量是等相关的，例如这里有效益值和背包容量两个限制条件，所以存储的数组就是二维数组，自此延伸思考可以知道如果再增加一个条件，这里需要开三维数组，自此，我们就可以得到y取不同值是从第i个物品开始放的所有情况的效益值了。

c板子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

template<class T>
//这里的yMax为wi
void Knapsack(T p[],int c,int n,T** f){
    //对于所有i和y计算f[i][y]
    //初始化f[n][]
    for(int y=0;y<=yMax;y++){
        f[n][y]=0;
    }
    for(int y=w[n];y<=c;y++){
        //初始化第一行
        f[n][y]=p[n]
    }
    //计算剩下的f
    for(int i=n-1;i>1;i--){
        for(int y=0;y<=yMax;y++){
            //都默认为不装入这个物品时为最大值
            f[i][y]=f[i+1][y]
        }
        for(int y=w[i],y<=c;y++){
            //这里的for循环中的条件已经保证了物品i可以放入了
            //比较装入和不装入哪个效益值更大取大值
            f[i][y]=max(f[i+1][y],f[i+1][y-w[i]]+p[i]);
        }
    }
    //i=1即单独讨论第一个物品放还是不放
    f[1][c]=f[2][c];
    if(c>=w[1]){
        f[1][c]=max(f[2][c],f[2][c-w[1]]+p[1]);
    }
}
//对比分析，实际上元组法就是这个思路，只不过是用线性表优化了空间复杂度而已

元组法

仔细回想刚刚的方法，你有没有发现这里有一个可以优化的地方，给定了背包容量c后你会发现无论怎么组合，上面的表中貌似并不是所有值都可以取到，并且上种方法伴随着c和n的增大，表的大小以可见得速度增大，虽然时间复杂度没有发生太大变化，但是空间复杂度就过于庞大了，所以我们在这里提出了一种新方法，他不仅仅解决了空间复杂性过大的缺陷，同时这种方法也适用于w为非整数的情况，那么让我们来看一看思路吧。

元组法是将f(i,y)的跳跃点以元组(y,f(i,y))的形式存储于一个线性表p(i)中，表p(i)中的元组(y,f(i,y))按y的增序排列，p(i)中的元组(a,b)表示一种装物品的方法{i,…,n}，能够以a<=y<a’(a’为下一元组的横坐标)，取得效益值b。那么在拥有了f(i+1,y)和p(i+1)以后，我们就可以得出f(i,y)的线性表p(i)，这种算法思路如下：f(i,y)的定义: f(i，y)=max{f(i+1,y),f(i+1,y-wi)+pi},首先需要从P(i+1)得到函数f*(i+1,y)=f(i+1,y-wi)+pi的元组集合Q,设(a,b)∈Q, 则(a-wi, b-pi)必为P(i+1)的元组,反之亦然. 所以,P(i+1)的每个元组(w,p)对应Q的一个元组(w+wi, p+pi)。Q的元组(u,v)代表装物品{i,…,n}的一种方案:以背包容量u,能得到效益值v。接下来，是一种算法从p(i+1)和Q得到f(i,y)的元组(即p(i)的元组)。

从P(i+1)和Q得到P(i)的元组:因P(i+1)和Q内元组均按w和p的增序排列，所以可用以前学过的merge算法进行合并。合并时使用以下支配(优选)规则：

至此，我们利用上述方法从p(n)逐渐向下推导至p(2)并舍弃被支配元组，得到p(2)后不再产生p(1),p(2)的最后一个元组是f(2,c)对应的元组，设p(2)中满足w+w1<=c的最后一个元组为(w,v)，则将v+p1和p(2)的最后一个元组对应的效益值p作比较，效益值大的即为优化效益值。

如果你没有看懂，没关系，我也没咋看懂😅😆，直接看例题就好理解啦~

例题1

n=5,c=10,w=[2,2,6,5,4],p=[6,3,5,4,6]

即求f(1,10),首先我们可以知道p(5)=[(0,0),(4,6)](即放入物品5以后的跳跃点集合)，Q=[(5,4),(9,10)](即加入物品4以后的跳跃点)，因为(5,4)代表一种方案，其效益值不如(4,6)(即不是最优效益值)，所以舍弃(5,4)，得p(4)。

上述方法我们可以转化成函数来更直观的观看，每一次加入物品，可以看成是函数向右上平移，然好merge合并就是取外交点，如下图：

​

在上图中加入物品4后我们发现(5,4)在原来p(5)折线的下方，而(9,10)在p(5)折线的上方，所以根据支配原则，(5,4)被舍弃，p(4)取所有折线的外围，得p(4)的图像如下

回想一下原理，我们知道p(4)表示的是从i=4开始放物品，随着y增大，p的曲线，其中折线为跳跃点，那么很容易理解，当Q(5,4)时表示的是在y取值5以上时放入物品4不放入5，但是此时放入5时可以得到更大的效益值，所以(5,4)这个方案不是最优效益组合，当然就被pass了，而y=9时，原先放入的是物品5，但是加上Q(5,4)后表示的就是在可以放入物品5的同时，还可以再放进4，此时效益值达到了10且此时y=9<=c(10)，所以p(4)在y>=9时取外围得到效益值为10，所以合并的含义就是根据只放入物品5时的折线(p(5))和只放入物品4时的折线(Q)，综合考虑得到最优的组合方案取外部折线得到的即位从物品4开始放时y取不同值时的最优效益解。

同理，根据上面的思路，p(4)=[(0,0),(4,6),(9,10)],加入物品3，此时Q=[(6,5),(10,11)]，之所以没有(15,15)，是因为背包容量不够，所以直接舍弃，合并得到p(3)=[(0,0),(4,6),(9,10),(10,11)]，然后放入物品2，得到p(2)=[(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)],最后再逐一加上物品1，发现(2,6)+(6,9)=(8,15)>(10,11),所以最终的效益值即为15，之所以不求p(1),是因为，此时得到的p(1)=[(0,0),(2,3),(4,6),(6,9),(8,15)]就是之前求得的Q，但是要注意这可不是表示的一组优化效益解😲，如果你认为这是一组优化解说明没有理解元组法哦，建议再反复思考一下，此时的p(1)应该表示的是从物品1开始放入，y取不同值时的最佳效益值，每一个值都代表了不同的组合方案！！所以我们现在虽然得到了y取不同值时的最佳优化效益值，以及容量c时的最大效益值，但是此时我们还并不会求优化解，即组合方案，别着急，后面我们会讲到，此时我们先复习一下，上题我们是自后而前推导的，那么下面这道题我们在自前而后推导一下，顺便检验一下是否真正理解透彻此方法。

例题2

n=4,c=20,w=(10,15,6,9),p=(2,5,8,1)

• P(1)={(0,0)},(10,2)},Q={(15,5)}
• P(2)={ (0,0)},(10,2), (15,5)},Q={(6,8),(16,10)}
• P(3)={(0,0),(6,8),(16,10)}

因(6,8)+(9,1)=(15,9),效益值为9，小于(16,10)的效益值10。所以优化的效益值为10。

回溯法求解最佳组合方案

如果你理解了不放入物品i时的递归式，会很容易发现，f(i,y)==(fi+1,y)，而回溯法也是利用了这个等式进行求解的。下面我们就以例题2为例回溯求解最佳组合方案。

首先g(4,20)(效益值为10)==g(3,20)(效益值为10),表示我们并没有放入物品4，然后g(3,20)(效益值为10)!=g(2,20)(效益值为5),所以说明放入了物品3后最佳效益值由5涨到了10，所以放入了物品3，此时y=c-w3=14，p=20-p3=2，所以变为g(2,14),然后g(2,14)(效益值为2) ==g(1,14)(效益值为2),所以没有装物品2，最后g(1,14)(效益值为2)!=0,说明装入了物品1，所以最佳组合为[1,0,1,0]。

矩阵乘法链

学过线性代数的同学都知道，不同的矩阵相乘方法，所用的乘法次数也是不同的，比如假定A为100×1矩阵,B为1×100矩阵,C为100×1矩阵,(A*B)*C需乘法数为100×1×100＋100×100×1＝20000而 A*(B*C) 所需乘法数为1×100×1＋100×1×1＝200,(温馨提示：m×n矩阵A与n×p矩阵B相乘需要做m*n*p个元素乘法,原因想一想就懂了)。

矩阵乘法链问题就是求得所用乘法次数最少的乘法顺序并求得最小乘法次数，我们考虑，每次Mi×…,×Mj (i<=j)，每次将这部分分成两部分，即取一个i<=k<=j，将矩阵乘法链分为M(i, k)×M(k+1,j)。那么计算M(i,j)的优化乘法顺序在计算子链M(i,k)和M(k+1,j)时的也是优化的。因此我们可以得到以下递归式：

用c(i,j)表示为计算M(i，j)的优化乘法数

$$c(i,j)=min\{c(i,k)+c(k+1,j)+Row_i*Row_{k+1}*Column_{j}\},i<=k<=j$$

并且kay(i,j)为c(i,j)达到最小值的k，并且c(i,i+1)表示Mi×Mi+1,即两个矩阵相乘无法在分隔可以求得具体数值，c(i,i)则表示一个矩阵即默认最后在乘所以次数为0，所以可以解题：

设q = 5和r =(10 , 5 , 1 , 10 , 2 , 10)，这里表示有5个矩阵，分别为10×5,5×1,1×10,10×2,2×10,所以根据动态规划的递归式得

c(1,5)=min{c(1,1)+c(2,5)+500,c(1,2)+c(3,5)+100,c(1,3)+c(4,5)+1000,c(1,4)+c(5,5)+200},这里c(3,5),c(2,5)都可以再次分隔。

c(2,5)=min{c(2,2)+c(3,5)+50,c(2,3)+c(4,5)+500,c(2,4)+c(5,5)+100}

c(3,5)=40,kay(3,5)=4,c(2,4)=30,kay(2,4)=2,所以在c(1,5)中,方案2，即从2第一次分隔锁的乘法次数最少为c(1,2)+c(3,5)+100=50+40+100=190,回溯法求得顺序：

M(1,5)=M(1,2)×M(3,5),M(3,5)=M(3,4)×M(5,5),所以最终顺序为[M(1,1)×M(2,2)]×{[M(3,3)×M(4,4)]×M(5,5)},最少乘法为190。

All-pair最短路问题

最短路径:假设G为有向图,其中每条边都有一个成本(cost),图中每条有向路径的长度(或成本)定义为该路径上各边的成本之和。对于每对顶点(i, j), 定义从i 到j 的所有路径中,具有最小长度的路径为从i 到j 的最短路。All-Pair最短路问题:求每对点间的最短路。假定图上无负成本的环路, 这时只需考虑简单路径: 加上环路只会增加路径成本。

我们的解题思路为将节点1到n进行任意顺序编号，然后定义c(i,j,k)表示为从i出发到节点j的路过的节点序号不超过k的最短路长度，即包含i,j和1,…,k的子图上的最短路。所以，c(i,k,k)=c(i,k,k-1),c(k,j,k)=c(k,j,k-1)并且对于所有的k,均有c(i,i,k)=0，特别的c(i,j,0)=cost(i,j)。

例如下图：

我们可以建立递推公式，即

$$c(i,j,k)=min\{c(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)\}$$

表示在最短路上或不包含k或包含k,如果直接用递归程序求解，则计算c(i,j,n)的复杂度会极高，所以这里利用迭代的方法暂存中途计算结果。

这里我们用迭代矩阵的方法求解，建立矩阵C(k)代表矩阵(c(i,j,k),i,j=1,…,n),因为c(i,i,k)=0，所以不用想矩阵的对角线元素均为0，然后算法迭代，初始化的C(0)即为图的邻接矩阵，即不经过任意中间节点从i到j的路径长度，不能到达即为∞，然后每次迭代时由于c(i,k,k)=c(i,k,k-1),c(k,j,k)=c(k,j,k-1)，所以矩阵C(k)的第k列和第k行的元素值不发生变化，即C(k)(i,k)=C(k-1)(i,k),C(k)(k,j)=C(k-1)(k,j),而其他行，列的元素则需要按照上面的递归式进行求解，C(k)(i,j)={C(k-1)(i,j),C(k-1)(i,k)+C(k-1)(k,j)},又因为C(k)=c(i,j,k),所以C(k-1)(i,k)=C(k)(i,k),C(k-1)(k,j),所以前面的式子可以改写为C(k)(i,j)={C(k-1)(i,j),C(k)(i,k)+C(k)(k,j)}，所以算法实现时即为每次跌倒第k个矩阵时，k行k列照抄前面的矩阵就好，其他的逐一用之前i->j的长度和新的i->k+k->j比较选短路径即可。如下图：

右边的即为邻接矩阵同时也就是C(0),接下来迭代，有几个点就迭代几次，上图3个点，所以迭代3次。

我们发现第一行和第一列都是直接照抄没变化，而C(1)(3,2)=min{C(0)(2,3),C(0)(3,1)+C(0)(1,2)},因为C(0)(3,2)=∞,而后者为7，所以更新C(1)(3.2)=7。然后迭代得C(2).

第二行和第二列照抄，然后C(2)(1,3)=min{C(1)(1,3),C(1)(1,2)+C(1)(2,3)}=min{11,4+2}=6

其他情况经计算无太大变化，然后迭代得C(3)。

第三行和第三列不变，检验其他的情况，发现

C(3)(1,2)=min{4,6+7}=4,所以这种情况不变，而C(3)(2,1)=min{6,2+3}=5所以更新，最后C(3)即为各个点之间最短路径权重，回顾整个过程，我们每一次迭代都是遵循了递归表达式，并且由于每次都将中间结果进行了暂时储存，所以也避免了重复的计算。

最长公共子序列

最大公共子序列问题和最大公共子串问题不一样，子序列并不要求是连续的，我们首先给出子串的定义。

思考:什么是子序列?

一个给定的序列的子序列就是将给定序列中零个或者多个元素去掉之后得到的结果，即元素不需要连续如下图：

所以最长公共子序列就是对于给定序列X和Y，需要找出一个子序列Z使得Z同时是X和Y的子序列并且还要是最长的，那么Z就是最长公共子序列又简称为LCS。那么如何求得最长公共子序列的长度呢？

思考：LCS长度求解的方法？

首先我们想到的就是暴力循环穷举来求得LCS的长度，但是显然时间复杂度为O(2^n)太大了，我们需要降低时间复杂度，所以寻找一种更好的方法即dp算法找到递归式即可，如下：

首先我们思考一个问题，对于两个给定序列A="a0,a1,…,am"和B="b0,b1,…,bn"他们的最长公共子序列为Z="z0,z1,…,zk"那么我们很容易得到如下规律：

• 如果am=bn且zk=am=bn，那么显然"z0,z1,…,z(k-1)"是"a0,a1,…,a(m-1)"和"b0,b1,…,b(n-1)"的一个最长公共子序列。
• 如果am!=bn且zk!=am，那么zk==bn,所以显然"z0,z1,…,zk"是"a0,a1,…,a(m-1)"和"b0,b1,…,bn"的一个最长公共子序列。
• 如果am!=bn且ak!=bn,那么zk==am，所以显然"z0,z1,…,zk"是"a0,a1,…,am"和"b0,b1,…,b(n-1)"的一个最长公共子序列。

所以我们可以列出以下递归式：其中C表示LCS长度，i,j是两个串的下标值

$$C(i,j)=\begin{cases} 0,&if&i=0orj=0\\ C[i-1，j-1],&if&i,j>0andx_i=y_i\\ max\{C[i,j-1],c[i-1,j]\}&if&i,j>0andx_i≠y_i \end{cases}$$

根据上面的式子我们也不难理解就是下面的情况：设

1. p1表示A的前i-1个字符和B的前j-1个字符的LCS的长度
2. p2表示A的前i个字符和B的前j-1字符的LCS的长度
3. p表示A的前i-1个字符和B的前j-1个字符的LCS的长度
4. p0表示A的前i个字符和B的前j个字符的LCS的长度

如果A的第i个字符和B的第j个字符相等，则p0=p+1

如果A的第i个字符和B的第j个字符不相等，则p0=max{p1,p2}

所以也是和上面的背包问题相似打表求解如下图，我们只要从C[0][0]开始打表，填到C[m][n]就是LCS的长度，那么具体做法如下：

首先我们需要将两个序列串的初始化，即表格的第零行和第零列填零（根据公式1，i或者j有一个为零时，LCS的长度都为0）：

这样我们接下来对每一个格的数值计算就是按照公式2和公式3展开，例如S1的3和S2的3相同所以他们的值(S11，S21)=(S10+S20)+1=(0,0)+(1,1)=(1,1)，所以表中(1,1)的位置处的值为1，即：

对于两个字符相等的地方他们的值来自左上角的值+1，而对于不相等的位置则根据公式3知道为左边的值和上边的值中最大的值决定，如下：

S1的3和S2的5不相同，所以根据公式3可以得到值来自黄格中较大的值，所以为1，这样我们对所有行进行填写，直至填满整个表（实际上代码中是使用二维数组来打表）。就可以得到如下：

所以我们求得整个表的所有值后最右下角的就是解，所以对于上面的这个序列串，最终的LCS长度就是C[8,9]=5，那么我们又怎样求得具体的LCS是什么呢？

思考：LCS具体求解的方法？

我们需要进行回溯求解，如下从C[8,9]开始分别和左，左上，上的三个格进行对比，相同的格子值就是来的路径也就代表了是根据公式几推得的，那么我们也就知道了求解时的情况，如下：

我们发现C[8,9]的值和C[8,8]的值相同，所以说明C[8,9]是由公式3推得的，所以说明S18和S29的元素不相同，而对于C[8,8]的值来自于C[7,7]是公式2推得的，所以说明C[8,8]所对应的S18和S28元素相同，这样我们就可以找到相同元素了如上图的棕色方块（所以就是如果这个方块K所对应的值和其左上角的格值相同则K所对应的坐标值是元素相同的一个坐标，否则就不是），如果不是相同元素即S1[i] != S2[j] 且遇到了c[i-1][j] = c[i][j-1]即左方块和上方块值相同时永远要取一个方向，要么都左，要么都上，这样我们一直到最左上方，所有棕色方块所组成的就是一个LCS，如上图中的每次都是取左最终得到的LCS是{3,4,6,7,8},而如果每次都取上方：

那么得到也是一个大小为5的LCS，是{3,5,7,7,8}。这种求解方法的时间复杂度仅仅为O(m+n)，空间复杂度也只是O(mn)很是简单高效。

拓展：另一种打表格式

对于上面这种打表直接求值很是难以直接方便看出回溯路径，所以我们知道了原理后可以得到一种更为简单的路径，即：

• 在对应字符相等的时候，用↖标记
• 在p1 >= p2的时候，用↑标记
• 在p1 < p2的时候，用←标记

这样我们得到的打表最终结果会如下：

这样我们就可以更好的找到回溯路径求得LCS了，并且如果可以同时添加上数值也就很容易能够同时求解得到LCS的长度。

小作业

Questions

1. 设c(i)为多段图上节点1到目的节点的最短路长度，试列出动态规划的递归式.并就课堂上的 例子给出求解过程。
2. 0/1背包问题: n=4,c=20,w=(10,15,6,9) p=(2,5,8,1) 请使用元组法求解该背包问题的优化值和优化解。
3. 子集和数问题:设S={s1,s2,…,sn} 为n个正数的集合,试找出和数不超过M且最大的S的子集, 该问题是NP-难度问题,试用动态规划法设计一算法。
4. 设一个矩阵乘法链的行列数为r=(10,20,50,1,100),用动态规划算法给出优化的乘法顺序和 优化的乘法数。

Answers

参考文献

结尾语

本节我们对dp算法有了深刻的了解，知道了解题过程，解题思路就是先建立递归表达式，然后找到已知条件，借助矩阵，线性表等数据结构进行中途结果的暂存，然后通过递归求解所有情况的优化值，那么本次分享就到这里😬！