理解DP

author: thy from buaa

初见

dynamic programming(可以理解为动态刷表法 其实这里的programming并不是编程而是规划、设计表格的意思) 关于动态规划的概念，算法导论已经说得很清楚了这里再说一点个人理解。

首先动态规划解决的问题具有如下三个特性：

1.最优子结构: 如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

2.无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3.有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

这三个性质在之后的讲解中会不断提到。

背包

记忆化搜索与动态规划——以01背包为例

有n个重量和价值分别为wi,vi的物品，从中挑选出总重量不超过W的物品，求所有方案中价值最大的

input:n = 4  (w,v) = {(2,3),(1,2),(3,4),(2,2)}W = 5

output:7 (select 0 1 3)

朴素方法

首先我们从最朴素的想法，看一看每个物品是否放入背包进行递归搜索：

int n,W;int w[MAX],v[MAX];//从第i个物品开始挑选总重小于j的部分int rec(int i,int j){    int res;    if(i == n){//没有剩余的物品了        res = 0;    }else if(j < w[i]){//无法挑选当前物品 跳过        res = rec(i+1,j)    }else{//可以选 那么选不选都试试        res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);        //rec(i+1,j) 不选 跳过选下一个        //rec(i+1,j-w[i])+v[i]选择当前的 占用了w[i]的体积 获得了v[i]的价值    }    return res;}

递归树如图

递归深度为n，每一层需要两个分支搜索，最坏情况是O(2^n )。

记忆化搜索

我们可以看到，圈中的地方有重复的计算，那么我们不妨记录一下每次递归的结果，如过需要重复计算直接拿来用。

int n,W;int w[MAX],v[MAX];int dp[MAX][MAX];//初始化为-1//从第i个物品开始挑选总重小于j的部分int rec(int i,int j){    if(dp[i][j] >= 0){        return dp[i][j];    }    if(i == n){//没有剩余的物品了        res = 0;    }else if(j < w[i]){//无法挑选当前物品 跳过        res = rec(i+1,j)    }else{//可以选 那么选不选都试试        res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);        //rec(i+1,j) 不选 跳过选下一个        //rec(i+1,j-w[i])+v[i]选择当前的 占用了w[i]的体积 获得了v[i]的价值    }    return dp[i][j]=res;//记录结果}

递归只有在第一次调用时会被执行，而i和j的组合一共只有nW种，故而只需O(nW)的复杂度即可解决，这种方式称为记忆化搜索。

抽化为动态规划

根据记忆化搜索的启示，不妨看一下记忆化数组。根据我们的递归搜索，记dp[i][j]为从第i个物品开始挑选总重小于等于j时，总价值的最大值。于是，有

\(dp[n][j]=0\\ dp[i][j]=\left\{ \begin{cases} &dp[i+1][j]\quad(j < w[i])\\ &max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])\quad (others)\\ \end{cases} \right.\)

公式看出选不选第i个物品是受到第i+1个物品影响的故而填表的时候是逆序的

i\j	0	1	2	3	4	5
0	0	2	3	5	6	7
1	0	2	2	4	6	6
2	0	0	2	4	4	6
3	0	0	2	2	2	2
4	0	0	0	0	0	0

int dp[MAX][MAX];int solve(){    for(int i=n-1;i>=0;i--){        for(int j=0;j<=W;j++){            if(j < w[i]) dp[i][j] = dp[i+1][j];            else dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);        }    }    return dp[0][W];}

由此 我们已经有了从记忆化书所中抽象出的动态规划表格了，但是我们定义的dp数组是逆推的，更为常见的定义如下：

\(dp[i+1][j]从0到i+1物品中选取总重不超过j的物品时最大的价值\\ dp[0][j]=0\\ dp[i+1][j]=\left\{ \begin{aligned} &dp[i][j]\quad(j < w[i])\\ &max(dp[i][j],dp[i][j-w[i]]+v[i])\quad (其他)\\ \end{aligned} \right.​\)

int dp[MAX][MAX];int solve(){    for(int i=0;i

空间上的优化

\(dp[i][j]​\)是由\(dp[i-1][j]和dp[i-1][j-w[i]]​\)两个子问题递推来的，这就要求我们倒序地以\(j:W\rightarrow w[i]​\)的顺序

来进行内层循环(如果是顺序的进行的话就相当于\(dp[i][j]\)由\(dp[i][j-w[i]]\)推导而来与题意不符合

至此，我们就得到了01背包的抽象过程

def ZeroOnePack(dp,v,w){    for j from W to w[i]        dp[j] = max(dp[j],dp[j-w]+v)}dp[0...W] memset to 0for i from 1 to n    ZeroOnePack(dp,v[i],w[i])

如果要求背包必须装满，那么初始化时候可以吧dp[1...n]数组初始化为-1(即负无穷),dp[0]=0，因为按照我们的定义，只有容量为0的背包在什么都不装的且价值为0的状态下被“装满“，其他都属于无解的非法状态

满背包代码

memset(dp,-1,sizeof(dp));dp[0] = 0;for(int i=0;i
    
     =cost[i];j--){        if(dp[j-cost[i]]!=-1 && dp[j] < dp[j-cost[i]]+value[i])            dp[j] = dp[j-cost[i]]+value[i];     }}
    

输入规格问题

如果输入的背包重量很大，极有可能造成数组过大MLE，复杂度O(nW),也有可能TLE，因此如果背包的容纳重量很大，但是物品总价值max_n*max_v很小，可以考虑对dp数组变形：

\(dp[i+1][j]\)前i个物品挑选价值总和为j时的最小重量，不存在时为INF

\(dp[i][j+1]=min(dp[i][j],dp[i][j-v[i]]+w[i])\)

最终答案是\(dp[n][j]<=W\)的最大的j这里就不给出代码了 读者自行验证即可。

完全背包

有n个重量和价值分别为wi,vi的物品，从中挑选出总重量不超过W的物品，求所有方案中价值最大的。每个物品可以挑选任意多件。

inputn = 3(w,v) = {(3,4),(4,5),(2,3)}W = 7output10 (0号选1件 2号选2件)

令\(dp[i+1][j]\)从前i种物品中挑选总重量不超过j时的价值最大值，那么递推关系为:

\(dp[0][j] = 0\)

\(dp[i+1][j] = max(dp[i][j-k*w[i]]+k*v[i]) \quad (k>=0)\)

按这个思路我们有朴素的如下代码：

int dp[MAX][MAX];int solve(){    for(int i=0;i

这构成了一个三重循环。k最多是从0到W，因此复杂度为O(nW^2),这样并不是我们所期待的。

i\j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	4	4	4	8	8
2	0	0	0	4	5	5	8	9
3	0	0	3	4	6	7	9	10

我们观察表格结合代码注意到，在\(dp[i+1][j]​\)中选择k个的情况，已经在\(dp[i][j-w[i]]​\)的计算中选择k-1个是相同的，所以在\(dp[i+1][j]​\)的递推中k>=1部分的计算已经在\(dp[i+1][j-w[i]]​\)的计算中完成了，由此我们有如下变形:

\(\quad dp[i+1][j] \\\)

\(= max(dp[i][j-k*w[i]]+k*v[i])\quad k>=0\\\)

\(= max(dp[i][j],max(dp[i][j-k*w[i]]+k*v[i]))\quad k>=1\\\)

\(=max(dp[i][j],max(dp[i][(j-w[i])-k*w[i]]+k*v[i])+v[i])\quad k>=0(相当于k+1代替k)\\\)

\(=max(dp[i][j],dp[i+1][j-w[i]]+v[i])\\​\)

这样一来，就无需k的循环了，可以在O(nW)时间内解决问题

int dp[MAX][MAX];int solve(){    for(int i=0;i

空间上的优化

只需要将01背包的内层循环倒过来即可。

仔细思考一下不难发现，之所以01背包要倒序进行内层循环，正是为了保证每个物品只能选择一次。而完全背包可以不限次数地选择，所以考虑加选第i件物品时，就有可能用上\(dp[i][j-w[i]]\)这个子结果，事实上，从上面减小时间复杂度的推导中也不难看出，我们用到了相同i循环下j循环之前的结果(即\(dp[i+1][j-w[i]]+v[i]\))，故而要求内层循环j从\(w[i]\)到W。

int solve(){    for(int i=0;i

于是我们也有了完全背包的抽象过程

def CompletePack(dp,v,w){    for j from w to W        dp[j] = max(dp[j],dp[j-w]+v)}dp[0...W] memset to 0for i from 1 to n    CompletePack(dp,v[i],w[i])

多重背包

有n个重量和价值分别为wi,vi的物品，从中挑选出总重量不超过W的物品，求所有方案中价值最大的。每个物品可以选择的件数不一，给出输入数组m,mi为第i件物品的件数。

此题和完全背包非常类似，同样地从朴素的方法出发，对于第i件物品有mi+1种策略，不取，取1件…取mi件，由此我们有：

\(dp[i+1][j]=max(dp[i][j-k*w[i]]+v[i])\quad 0<=k<=m[i]\)

同样的三层循环，并不是我们想要的效果，必须要优化。

优化一

引用自崔添翼巨巨的背包九讲

将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1; 2; 2^2 ; 2^(k-1);m[i]-2^k + 1，且k 是满足m[i]-2^k + 1 > 0 的最大整数。例如，如果m[i]为13，则相应的k = 3，这种最多取13 件的物品应被分成系数分别为1; 2; 4; 6 的四件物品。分成的这几件物品的系数和为m[i]，表明不可能取多于Mi 件的第i 种物品。另外这种方法也能保证对于0到m[i]间的每一个整数，均可以用若干个系数的和表示。这里算法正确性的证明可以分0 ... 2^(k-1) 和2^k...m[i] 两段来分别讨论得出，希望读者自己思考尝试一下。这样将第i种物品分成了O(logm[i])种，复杂度转化为O(W∑logm[i])

代码如下：

#include
    
     using namespace std;int v,n;int value;int cost;int m;int dp[30005];void zeroPack(int cost,int value){    for(int j=v;j>=cost;j--){        if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value;    }}void completePack(int cost,int value){    for(int j=cost;j<=v;j++){        if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value;    }}int main(){    int t; cin>>t;    while(t--){        cin>>v>>n;        for(int i=0;i
     
      >value>>cost>>m;            if(cost*m >= v){                completePack(cost,value);                continue;            }            int k=1;            while(k < m){                zeroPack(k*cost,k*value);                m = m-k;                k *= 2;            }            zeroPack(m*cost,m*value);        }        cout<
      
       <
      
     
    

可行性问题

引用自崔添翼巨巨的背包九讲

当问题是“每种有若干件的物品能否填满给定容量的背包”，只须考虑填满背包的可行性，不需考虑每件物品的价值时，多重背包问题同样有O(nW) 复杂度的算法。设dp[i][j]表示“用了前i 种物品填满容量为j 的背包后，最多还剩下几个第i种物品可用”，如果dp[i][j] = -1 则说明这种状态不可行，若可行应满足0<=dp[i][j]<=m[i]递推求dp[i][j]的伪代码如下：dp[0][1...V] = -1;dp[0][0] = 0;for i from 1 to N    for j from 0 to W        if dp[i-1][j] >= 0            dp[i][j] = m[i];        else            dp[i][j] = -1;    for j from 0 to W-w[i]        if dp[i][j] > 0            dp[i][j+w[i]] = max{dp[i][j+w[i]],dp[i][j]-1}最终dp[n][0...V ]便是多重背包可行性问题的答案。

组合背包

有n个重量和价值分别为wi,vi的物品，从中挑选出总重量不超过W的物品，求所有方案中价值最大的。每个物品可以选择的件数不一，给出输入数组m,mi为第i件物品的件数，其中有的物品可以取一次，有的可以不限次数取，有的与可取数目限制。

有了前面的讲解，我们只需要封装好01背包，完全背包和多重背包的函数，再分类讨论即可

伪代码:

for i = 1 to N    if 第i件物品属于01背包        ZeroOnePack(F,Ci,Wi)    else if 第i件物品属于完全背包        CompletePack(F,Ci,Wi)    else if 第i件物品属于多重背包        MultiplePack(F,Ci,Wi,Ni)

参考代码(233代表可以无限取)：

#include
    
     #include
     
      using namespace std;int v,n;int value;int cost;int m;int dp[30005];void zeroPack(int cost,int value){    for(int j=v;j>=cost;j--){        if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value;    }}void completePack(int cost,int value){    for(int j=cost;j<=v;j++){        if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value;    }}void multiPack(int cost,int value){    if(cost*m >= v){        completePack(cost,value);        return;    }    int k=1;    while(k < m){        zeroPack(k*cost,k*value);        m = m-k;        k *= 2;    }    zeroPack(m*cost,m*value);}int main(){int t; cin>>t;    while(t--){        cin>>v>>n;        for(int i=0;i
      
       >value>>cost>>m;            if(m == 233){                completePack(cost,value);            }            else if(m == 1){                zeroPack(cost,value);            }            else{                multiPack(cost,value);            }        }        cout<
       
        <
       
      
     
    

算法导论中的经典例子

钢管切割(类背包问题)

给定一段长度为n英寸的钢条和一个价格表\(p_i\)求切割钢条方案，使得销售利益\(r_n\)最大(有可能完全不需要切割)

对于长度为i的钢条，我们用变量j遍历钢条能被切割成的每一个可能长度，用dp[i]表示长度为i的钢条经过某种切割所能获得的最大利益，那么\(dp[i] = max(dp[i],dp[i-j]+p[j])\)

对于此题有两种动归思路。

第一种思路是带备忘录的自顶向下法，亦即记忆化搜索的方法，把已知结果的子问题的解保存下来，下次直接使用，复杂度\(O(nW)\)

dp[0...n] memset to -1def memorized_cutrod(p,n,dp):    if  dp[n]!=-1 return dp[n]    if  n == 0 q = 0    else        q = -1        for i=1 to n:            q = max(q,p[j]+memorized_cutrod(p,n-i,r))    return dp[n] = q

第二种思路是自底向上法，即使用循环对dp数组进行更新来“刷表”，时间复杂度\(O(n^2)\)

dp[n]def bottom_up_cut_rod(p,n):    dp[0] = 0    for i=1 to n:        q = -1        for j=1 to i:            q = max(q,p[j]+dp[i-j])        dp[i] = q;return dp[n]

矩阵链乘(区间dp)

给定一个n个矩阵的序列\(<A_1,A_2,...,A_n>\)希望求它们的乘积A1A2A3···An

由于矩阵乘法满足结合律，因此任何加括号的方法都会得到相同的计算结果。

首先给出完全括号化矩阵的定义：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积，且已外加括号。

如对于\(<A_1,A_2,A_3,A_4>\)矩阵链，共有五种完全括号化的方法:

\((A_1(A_2(A_3A_4)))\)

\((A_1((A_2A_3)A_4)))\)

\(((A_1A_2)(A_3A_4))\)

\(((A_1(A_2A_3))A_4)\)

\((((A_1A_2)A_3)A_4)\)

我们需要求得一个完全括号化方案使得矩阵链乘的所需乘法次数最小。

第一步 寻找最优子结构

对于其子问题，选定一个矩阵序列\(A_iA_{i+1}...A_j\)进行括号化，我们必须在某个\(A_k\)和\(A_{k+1}\)之间把矩阵分开，然后再计算它们的乘积得到最终结果\(A_{i·j}\)。这种方案的计算代价等于\(A_{i·k}\)的计算代价加上\(A_{k+1·j}\)的计算代价，再加上两者乘积的计算代价。同时，我们必须保证在确定分割点时候，已经考察了所有可能的分割点，这样保证不会遗漏最优解。

第二步 自底向上计算

j-i+1个矩阵相乘的最右计算代价dp[i,j]只依赖于少于i-j+1和矩阵链乘的最优计算代价。也就是说，对\(k=i,i+1,...,j-1\)矩阵\(A_{i,k}\)是\(k-i+1<j-i+1\)个矩阵的积，矩阵\(A_{k+1,j}\)是\(j-k<j-i+1\)个矩阵的乘积。因此，算法按照长度递增的顺序求解矩阵链乘的括号化问题，并按顺序填表。这其实也是区间dp的思想 复杂度\(O(n^3)\)

int n;long long matrix[305];long long m[305][305];long long s[305][305];void matrix_chain_order(){    for(int l=2;l<=n;l++){        for(int i=1;i<=n-l+1;i++){            int j = i+l-1;            m[i][j] = INT_MAX;            for(int k=i;k<=j-1;k++){                int q = m[i][k]+m[k+1][j]+matrix[i-1]*matrix[k]*matrix[j];                if(q <= m[i][j]){                    m[i][j] = q;                    s[i][j] = k;                }            }        }    }}

最长公共子序列

给定一个序列\(X=<x_1,x_2,...,x_m>\)和\(Z=<z_1,z_2,...,z_k>\)满足下列条件时候称为X的子序列，进存在一个严格递增的X的下标序列\(<i_1,i_2,...,i_k>\)对所有的\(j=1,2,...,k\)满足\(x_{i_J}=z_j\)。例如\(Z=<B,C,D,B>\)是\(X=<A,B,C,B,D,A>\)的子序列。

最长子序列问题，就是要寻找\(X=<x_1,x_2,...,x_m>\)和\(Z=<z_1,z_2,...,z_k>\)两个给定序列的最长的公共子序列。简称LCS

第一步 刻画LCS的最优子结构

给定序列\(X=<x_1,x_2,...,x_m>\)和\(Y=<y_1,y_2,…,y_n>\)，\(Z=<z_1,z_2,...,z_k>\)为X和Y的任意LCS

1.如果\(x_m = y_n\)，则\(z_k=x_m=y_n\)且\(Z_{k-1}\)是\(X_{m-1}\)和\(Y_{n-1}\)的一个LCS

2.如果\(x_m \ne y_n\)，则\(z_k \ne x_m\)且\(Z_{k-1}\)是\(X_{m-1}\)和\(Y\)的一个LCS

3.如果\(x_m \ne y_n\)，则\(z_k \ne y_n\)且\(Z_{k-1}\)是\(X\)和\(Y_{n-1}\)的一个LCS

第二步 计算LCS长度

\(dp[i][j]=\begin {cases} 0 &i=0 \; or \; j=0 \\ dp[i-1][j-1] &i,j>0 \;and \; x_i=y_j \\max(dp[i][j-1],dp[i-1][j]) &i,j>0 \; and\;x_i \ne y_j\end{cases}​\)

时间复杂度\(O(n^2)​\)

//下标从1开始for(int i=1;i

最优二叉搜索树(区间dp)

给定一个n个不同关键字的已排序的序列\(K=<k_1,k_2,...,k_n>\)，我们希望用这些关键字构造一颗二叉搜索树。对每个关键字\(k_i\)，都有一个概率\(p_i\)表示其搜索频率。有些搜索的值可能不在K中，因此我们还要有n+1个伪关键字\(d_0,d_1,...,d_n\)表示不在K中的值。\(d_0\)表示所有小于\(k_1\)的值，\(d_n\)表示所有大于\(k_n\)的值，对\(i=1,2,...,n-1\)，伪关键字\(d_i\)表示所有在\(k_i\)和\(k_{i+1}\)之间的值。对每个伪关键字\(d_i\)，都有一个概率\(q_i\)表示其搜索频率

我们知道了每个关键字和伪关键字的搜索概率，因而可以确定在一颗给定的二叉搜索树T中进行一次搜索的期望代价

E[T中搜索代价]

=\(\sum_{i=1}^{n}(depth_T(k_i)+1)*p_i+\sum_{i=0}^{n}(depth_T(d_i)+1)*q_i\)

=\(1+\sum_{i=1}^{n}(depth_T(k_i)*p_i+\sum_{i=0}^{n}(depth_T(d_i)*q_i)\)

步骤一 构造最优子结构

考虑一颗二叉搜索树的任意子树。它必须包含关键字\(k_i,...,k_j​\)的子树T‘，则T’必然是包含关键字\(k_i,...,k_j​\)和伪关键字\(d_{i-1},...,k_j​\)的子问题的最优解。对于这个序列中某个关键字，例如\(k_r​\)，是根节点，则其左子树包含关键字\(k_i,...,k_{r-1}​\)，而右子树包含关键字\(k_{r+1},...,k_j​\)。对于可能出现的空子树问题，例如序列\(ki,...,k_j​\)，如选定\(k_i​\)为根节点，则其左子树不包含任何关键字，但包含唯一的伪关键字\(d_{i-1}​\)。

步骤二 自底向上计算

对于包含关键字\(k_i,...,k_j\)的子树 概率之和为\(w(i,j)=\sum_{l=i}^{j}p_l+\sum_{l=i-1}^{j}q_l\)

因此若\(k_r\)为包含关键字\(k_i,...,k_j\)的最右二叉搜索树的根节点，我们有

\(dp[i][j]=p_r+(dp[i][r-1]+w[i][r-1])+(dp[r+1][j]+w[r+1][j])\)

注意\(w[i][j]=w[i][r-1]+p_r+w[r+1][j]\)

因此\(dp[i][j]=dp[i][r-1]+dp[r+1][j]+w[i][j]\)

最终我们有

\(dp[i][j]=\begin{cases} q_{i-1} &j=i-1\\ min_{i \le r \le j} \{dp[i][r-1]+dp[r+1][j]+w[i][j]\}&i \le j \end{cases}\)

这与矩阵相乘相类似都是利用区间dp的思想，枚举每一个区间长度，在长度内进行计算，最终\(dp[1][n]\)的值即为最终结果。

for(int i=1;i<=n+1;i++){    dp[i][i-1] = q[i-1];    w[i][i-1] = q[i-1];}for(int l=1;l<=n;l++){    for(int i=1;i<=n-l+1;i++){        int j = i+l-1;        dp[i][j] = INT_MAX;        w[i][j] = w[i][j-1]+p[j]+q[j];        for(int r=i;r<=j;r++){            double t = dp[i][r-1]+dp[r+1][j]+w[i][j];            if(t < dp[i][j]) dp[i][j] = t;        }    }   }

参考文献

《算法导论》

《挑战程序设计竞赛(第二版)》

《背包九讲》