DP解LCS问题模板及其优化

r囧r小猫 2021-12-21 01:07 158阅读 0赞

LCS--Longest Common Subsequence，即最长公共子序列，一般使用DP来解。

常规方法：

dp\[i\]\[j\]表示字符串s1前i个字符组成的字符串与s2前j个字符组成的字符串的LCS的长度，则当s1\[i-1\]==s2\[j-1\]时，dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1，否则dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i\]\[j-1\])。

最终的dp\[len1\]\[len2\]即最终答案。代码如下：

1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 char s1[505],s2[505];
     7 int len1,len2;
     8 int dp[505][505];
     9 
    10 int main(){
    11     while(~scanf("%s%s",s1,s2)){
    12         len1=strlen(s1),len2=strlen(s2);
    13         for(int i=0;i<=len1;++i) dp[i][0]=0;
    14         for(int i=0;i<=len2;++i) dp[0][i]=0;
    15         for(int i=1;i<=len1;++i)
    16             for(int j=1;j<=len2;++j)
    17                 if(s1[i-1]==s2[j-1])
    18                     dp[i][j]=dp[i-1][j-1]+1;
    19                 else
    20                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    21         printf("%d\n",dp[len1][len2]);
    22     }
    23     return 0;
    24 }

如果需要打印路径：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 char s1[505],s2[505];
     7 int len1,len2;
     8 int dp[505][505],path[505][505];
     9 
    10 void print(int p1,int p2){
    11     if(p1==0||p2==0) return;
    12     else{
    13         if(path[p1][p2]==1) print(p1-1,p2-1),printf("%c",s1[p1-1]);
    14         else if(path[p1][p2]==2) print(p1-1,p2);
    15         else print(p1,p2-1);
    16     }
    17 }
    18 
    19 int main(){
    20     while(~scanf("%s%s",s1,s2)){
    21         len1=strlen(s1),len2=strlen(s2);
    22         for(int i=0;i<=len1;++i) dp[i][0]=0;
    23         for(int i=0;i<=len2;++i) dp[0][i]=0;
    24         for(int i=1;i<=len1;++i)
    25             for(int j=1;j<=len2;++j)
    26                 if(s1[i-1]==s2[j-1])
    27                     dp[i][j]=dp[i-1][j-1]+1,path[i][j]=1;
    28                 else if(dp[i-1][j]>=dp[i][j-1])
    29                     dp[i][j]=dp[i-1][j],path[i][j]=2;
    30                 else
    31                     dp[i][j]=dp[i][j-1],path[i][j]=3;
    32         printf("%d\n",dp[len1][len2]);
    33         print(len1,len2);
    34         printf("\n");
    35     }
    36     return 0;
    37 }

空间优化：

如果只需要求LCS的长度，实际上只需要dp\[n\]就行了，应用滚动数组。因为dp\[i\]\[j\]由dp\[i-1\]\[j-1\],dp\[i-1\]\[j\],dp\[i\]\[j-1\]，用dp\[j\]表示dp\[i\]\[j\]，则更新dp\[j\]时用pre存储dp\[i-1\]\[j-1\]，此时的dp\[j-1\]表示dp\[i\]\[j-1\]，此时的dp\[j\]表示dp\[i-1\]\[j\]，这样就大大优化了空间，详见代码：

1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 char s1[505],s2[505];
     7 int len1,len2,pre,tmp;
     8 int dp[505];
     9 
    10 int main(){
    11     while(~scanf("%s%s",s1,s2)){
    12         len1=strlen(s1),len2=strlen(s2);
    13         memset(dp,0,sizeof(dp));
    14         for(int i=1;i<=len1;++i){
    15             pre=0;
    16             for(int j=1;j<=len2;++j){
    17                 tmp=dp[j];
    18                 if(s1[i-1]==s2[j-1])
    19                     dp[j]=pre+1;
    20                 else
    21                     dp[j]=max(dp[j-1],dp[j]);
    22                 pre=tmp;
    23             }
    24         }
    25         printf("%d\n",dp[len2]);
    26     }
    27     return 0;
    28 }

时间优化：

据说可以将LCS转换为LIS解法，从而使时间复杂度降为O(nlogn)，但似乎在某些特殊情况复杂度比常规做法更麻烦，不被建议使用。等以后接触时再更......

转载于:https://www.cnblogs.com/FrankChen831X/p/10423287.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/83df3c4195e14b9f8d1f7b392bc931ee.png