使用递推关系的动态规划dp解决问题（最长公共子序列和完全背包问题）

最长公共子序列问题

问题：
给定两个字符串$S_1{S}_2\dots \dots S_1$和$t_1{t}_2\dots \dots t_n$ 。求出这两个字符串最长公共子序列的长度。字符串$S_1{S}_2\dots \dots S_n$ 的子序列可以表示为
$S_{i1}{S}_{i2}\dots \dots S_{im}(i1<i2<\dots \dots im)$的序列。

限制条件
$1⩽n⩽1000$

输入样例：
n=4
m=4 //n、m分别为两个字符串的长度
s=“abcd”
t=“becd”

输出样例
3（”bcd“）

这个问题是经典的最长公共子序列问题。虽然算法不难实现，但是我们今天将尝试使用动态规划来解决此问题。
dp[i][j] :=s1……si 和 t1……tj对应的LCS的长度，
由此，$s_1\dots \dots s_{i+i}$ 和 $t_1\dots \dots t_{j+1}$对应的公共子列可能是下列三者中的一个：

• 当$s_{i+1}=t_{j+1}$时，在$s_1\dots \dots s_i$和$t_1\dots \dots t_j$的公共子列末尾加-上$s_{i+1}$
• $s_1\dots \dots s_i$和$t_1\dots \dots t_{j+1}$的公共子列
• $s_1\dots \dots s_{i+1}$和$t_1\dots \dots t_j$的公共子列

所以有以下递推关系成立：

$$dp[i+1][j+1]=\{\begin{array}{r}max(dp[i][j]+1,dp[i][j+1],dp[i+1][j]),(s_{i+1}=t_{j+1})\\ max(dp[i][j+1],dp[i+1][j]),(其他)\end{array}$$

分析可发现：$dp[i+1][j+1]=max(dp[i][j]+1,dp[i][j+1],dp[i+1][j])$其实可以直接换成：
$dp[i+1][j+1]=dp[i][j]+1$

公式的时间复杂度为$O(nm)$公式中dp[n][m]表示的就是LCS的长度。

代码如下所示：

#include <iostream>
#define MAX_N 10000
#define  MAX_M 10000

using namespace std;


int n ,m;
char s[MAX_N] , t[MAX_M];
int dp[MAX_N+1][MAX_M+1];


void init(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>s[i];

    for(int i=0;i<m;i++)
        cin>>t[i];
}

void solve(){
    for(int i=0 ;i<n ; i++){
        for(int j=0;j<m;j++){
            if(s[i]==t[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }else{
                dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    cout<<dp[n][m];
}

int main(){
    init();
    solve();
    return 0;
}	

进一步探讨递推关系

完全背包问题

问题：完全背包问题
有n种重量和价值分别为$w_i,v_i$的物品。从这些物品中挑选总重量不超过w的物品，求出挑选物品的总价值的最大值。在这里，每种物品可以任意选多件。
限制条件

• $1⩽n⩽100$
• $1⩽w_i,v_i⩽100$
• $1⩽W⩽1000$

输入样例：
n=3
(w,v)={(3,4), (4,5), (2,3)}
w=7
输出样例：
10（0号物品选1个，2号物品选两个）

这了例题中，和之前的不同之处在于每种物品可以选任意多个。

[上一个背包问题]https://blog.csdn.net/qq_28120673/article/details/81037700

首先尝试写出递推关系式
设dp[i+1][j] 表示从前i种物品中总重量不超过j的最大总价值。那么递推关系为：
$dp[0][j]=0$
d p [ i + 1 ] [ j ] = m a x { d p [ i ] [ j − k × w [ i ] ] + k × v [ i ] ∣ 0 ⩽ k } dp[i+1][j]=max{dp[i][j-k times w[i]]+ k times v[i] | 0leqslant k} dp[i+1][j]=max{dp[i][j−k×w[i]]+k×v[i]∣0⩽k}

#include <iostream>
#define MAX_N 100
#define  MAX_M 100

using namespace std;


int  n,W;
int w[MAX_N],v[MAX_N];
int dp[MAX_N+1][MAX_M+1];


void init(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    cin>>W;
}

void solve(){
  for(int i=0;i<n;i++){
      for(int j=0;j<=W;j++){
          for(int k=0;k*w[i] <= j; k++){
              dp[i+1][j]=max( dp[i+1][j],dp[i][j-k*w[i]]+k*v[i] );
          }
      }
  }
  cout<<dp[n][W];
}

int main(){
    init();
    solve();
    return 0;
}

该算法的核心为三重循环

for(int i=0;i<n;i++){
      for(int j=0;j<=W;j++){
          for(int k=0;k*w[i] <= j; k++){
              dp[i+1][j]=max( dp[i+1][j],dp[i][j-k*w[i]]+k*v[i] );
          }
      }
  }

需要注意的是，dp[i][j],表示的是选取i个物品种类，当i等于0时表示没有选物品，此时dp[0][j]=0,这个值的设定是在数组初始化就设置的，其目的为递推提供初始值。j表示物品的总重量，很显然物品的重量不能是负数，所以j-kw[i]>=0, 即第三个循环中kw[i]<=j;
显而易见的是前两个循序是遍历所有物品种类和数量的组合（这里并不是排列，可以想成将物品按编号从1～n排列。i表示只从编号1～i中抽取物品，编号在这范围内可以抽也可以不抽，），然后第三个循环不容易理解（花了我半天的时间才看懂，泪奔～～～）。
$dp[i+1][j]=max(dp[i+1][j],dp[i][j-k\ast w[i]]+k\ast v[i]);$
分析：
首先回顾一下示例数据：
n= 3
( w, v ) = { (3,4), (4,5), (2,3) }
w = 7

假如dp[i][0~n]的最大值已经求出当，当我们要求dp[i+1][…]的时候（实际上当求dp[i+1][…]的时候，dp[i][…]已近求出）可以认为是在挑选k件i号物品后，然后在前i件物品中挑选，显然dp[i][…]最大值我们已近知道，所以选出k*v[i]+dp[i][…]的最大值就是dp[i+1][…]的最大值。

下面分析递推过程：

1. dp[1][0]
   当j=0；每个物品的重都大于0，所以，k=0时，dp[1][0]=dp[0][0]=0;
   同理，可得，dp[1][1]=dp[1][2]=0;

2. dp[1][3]
   当k=0，dp[1][3]=dp[0][3]=0;
   当k=1，dp[1][3]=dp[0][13]+14=4;
   当k=2… ,k*w[i]>3

3. dp[2][0]
   显然j=0,1,2时dp[i][j]=0;

4. dp[2][3]
   当k=0，dp[2][3]=0;
   当k=1，dp[2][3]=dp[1][3-13]+13=3;
   当k为其他值时，k*w[1]>j;
   同理我们可以求出dp[2][4]=dp[2][5]=5, dp[2][6]=8, dp[2][7]=9。

5. dp[3][0]
   因为w[2]=2，所以，dp[3][0]=dp[3][1]=0;

6. dp[3][2]
   当k=1，kw[2]=2<=j , 所以dp[3][2]=dp[2][2- 12]+v[2]=3;
   当k=其他值时，均超出范围。

7. dp[3][3]
   当k=0,dp[3][3]=dp[2][3]=4;
   当k=1, dp[3][3]=dp[2][1]+v[2]=3;
   当k=其他值将超出范围；
   所以dp[3][3]最大值为3.
   8.dp[3][4]
   当k=0, dp[3][4]=dp[2][4]=5;
   当k=1，dp[3][4]=dp[2][4-12]+v[2]=dp[2][2]+3=3;
   当k=2，dp[3][4]=dp[2][4-22]+2v[2]=dp[2][0]+2v[2]=6;
   当k=其他值，将超出范围控制。

   同理可以得出dp[3][5]=7,dp[3][6]=7,dp[3][7]=10。

优化完全背包问题

并不是这样，其实我们还可以进一步优化它。
上面的算法中我们使用了三重循环。k的循环最大为W，所以最大时间复杂度为$O(n{W}^2)$ 。该算法中其实有一些多余的计算，接下来我们将多余的计算去除。
在dp[i+1][j]的计算中选择k(k>=1)个的情况，与dp[i+1][j-w[i]]中选择k-1的情况是相同的，所以dp[i+1][j]的递推式中k>=1的部分在计算中已经在dp[i+1][j-w[i]]的计算中完成了。为啥会这样呢，这个问题要从dp[][]的意义分析，dp[i+1][j-w[i]]表示在前i+1个物品中选择，即0～i号物品中选择。j-w[i]表示已选择一个i号物品，所以当k>=1时，一定至少选择了一个i号物品。说以dp[i+1][j-w[i]] ，包含了dp[i+1][j-k*w[i]],(k>=1)的情况。

可以根据递推公式看出：
d p [ i + 1 ] [ j ] = max ⁡ { d p [ i ] [ j − k × w [ i ] ] + k × v [ i ] ∣ 0 ⩽ k } = max ⁡ { d p [ i ] [ j ] , max ⁡ { d p [ i ] [ j − k × w [ i ] ] + k × v [ i ] ∣ 1 ⩽ k } ， 一 个 不 选 或 者 至 少 选 择 一 个 = max ⁡ { d p [ i ] [ j ] , max ⁡ { d p [ i ] [ j − w [ i ] − k × w [ i ] ] + k × v [ i ] ∣ 0 ⩽ k } + v [ i ] } = max ⁡ { d p [ i ] [ j ] , d p [ i + 1 ] [ j − w [ i ] ] + v [ i ] } begin{aligned} dp[i+1][j] & = max{dp[i][j-ktimes w[i]] + k times v[i] | 0 leqslant k } \ & =max { dp[i][j], max{ dp[i][j- k times w[i] ] + k times v[i] | 1 leqslant k } ，一个不选或者至少选择一个 \ & =max{ dp[i][j], max{ dp[i][j - w[i] - k times w[i] ] +k times v[i] | 0 leqslant k } + v[i] } \ & =max { dp[i][j],dp[i+1][j-w[i]] +v[i] } end{aligned} dp[i+1][j]​=max{dp[i][j−k×w[i]]+k×v[i]∣0⩽k}=max{dp[i][j],max{dp[i][j−k×w[i]]+k×v[i]∣1⩽k}，一个不选或者至少选择一个=max{dp[i][j],max{dp[i][j−w[i]−k×w[i]]+k×v[i]∣0⩽k}+v[i]}=max{dp[i][j],dp[i+1][j−w[i]]+v[i]}​

改进后代码如下：

void solve2(){
    for(int i=0;i<n;i++){
        for(int j=0;j<=W;j++){
            if(j<w[i]){
                dp[i+1][j]=dp[i][j];
            }else{
                dp[i+1][j]=max(dp[i][j], dp[i+1][j-w[i]] +v[i]);
            }
        }
    }
    cout<<" n"<<dp[n][W] <<"n";
}

简化01背包和完全背包

根据递推关系式可以知道dp数组可以直接使用1维数组就可以。

1. 01背包问题
   
   由图可知递推关系的每一行只与它的上一行有关系，所以我们可以每次跟新一行就覆盖上一行。

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

2. 完全背包问题

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

最后

以上就是善良小霸王为你收集整理的使用递推关系的动态规划dp解决问题（最长公共子序列和完全背包问题）的全部内容，希望文章能够帮你解决使用递推关系的动态规划dp解决问题（最长公共子序列和完全背包问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。