动态规划入门2（LCS模板）_c++ lcs模版

技术文档

动态规划入门2（LCS）

基本思路

在做这种类型的题目时我们需要注意

明确题目要求的状态

一般来说题目问什么，我们的dp[]数组就可以用来表示什么
状态之间的转移变换

当下状态是由那些状态转移而来的（枚举每一项操作）
状态的初始值和题目要求的输出

设f(i,j)表示只考虑 A的前 i个元素和B的前j个元素时的最长公共子序列的长度

求这时的最长公共子序列的长度就是 子问题；f(i,j)就是我们所说的状态，则f(n,m)是最终要达到的状态，即为所求结果。

对于每个f(i,j)，存在三种决策：

如果A[i]==B[j]，则可以将它接到公共子序列的末尾；
选择去接B而跳过A
选择去接A而跳过B

（通过比较上一步的长度来在操作2和操作3中选择）

所以就可以推出状态转移方程

如果A[i]==B[j]，f(i,j)=f(i-1,j-1)+1
不等的话，f(i,j) = max(f[i - 1][j], f[i][j - 1])

时间复杂度是O(n²)，当然也可以利用二分去优化_{但是我还不会}

可以通过这个SourceForge 的 LCS 交互网页更直观的看到dp的过程；

回文字串（模板）

题目原文

[P1435 IOI 2000] 回文字串 - 洛谷

思路分析

对上面模板的简单运用；

我们需要判断删掉几位后能构成回文字串；所以就是找这个字串和反向的这个字串的公共子序列有多少；最后长度减去公共的部分就是需要删除的字符数；

代码实现

#includeusing namespace std;#define int long long#define endl \'\\n\'const int N=1e4;int dp[N][N];signed main(){string a;cin>>a;string b=\' \'+a; // 这里在前面加个空格方便下标从1开始reverse(a.begin(),a.end()); // 倒置a=\' \'+a;for(int i=1;i<a.size();i++){for(int j=1;j<b.size();j++){ //模板if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<a.size()-1-dp[a.size()-1][b.size()-1]; // 输出删除的个数}

编辑距离

题目原文

P2758 编辑距离 - 洛谷

思路分析

这题和上面的也比较类似，但是更复杂一些；

要求我们把两个字符串变成一样的；我们有三种操作增加，删除和更改；

还是按照我们上面的基本思路

首先明确dp的状态：在这题我们可以用来表示第一个字符串到i的位置和第二个字符串到j的位置，此时的编辑距离（最小的编辑次数）

然后明确状态的转移

如果当前a[i]=b[j]，那么就不需要操作；此时dp[i][j]=dp[i-1][j-1]
如过不相等就需要来判断我们的三种操作
- 改：随边改一个就行，就一步在前面的基础上多一步让这位相等就行，也就是dp[i-1][j-1]+1
- 插入和删除：本质上是差不多的，都是对其中一个串进行操作使当前位相同；为了让操作更少我们就可以选min(dp[i-1][j]+1,dp[i][j-1]+1)
每次操作后都让步数京可能的小所以我们取三个操作中的最小值即可；

这题和上面的不同点还有初始状态的不同

上面的问题都是求最大所以初始为0就行，这里我们需要求最小所以先将数组初始化最大值；当其中一个字串为空时，另一个字串的长度就是需要更改（都是删除）的次数，所以dp的第0行和第0列也需要初始化；

代码实现

#includeusing namespace std;#define int long long#define endl \'\\n\'const int N=1e4;int dp[N][N];signed main(){string a,b;cin>>a>>b;a=\' \'+a;// 这里在前面加个空格方便下标从1开始b=\' \'+b;int n1=a.size();int n2=b.size();memset(dp,INT_MAX,sizeof a); //初始化for(int i=0;i<n1;i++)dp[i][0]=i;for(int i=0;i<n2;i++)dp[0][i]=i;for(int i=1;i<n1;i++){ // 模板for(int j=1;j<n2;j++){if(a[i]==b[j]) //相等时不用操作dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1)); // 取小的那个值}}cout<<dp[n1-1][n2-1];}

当然这些都只是O(n²)的做法，等日后精进了自己的技术后在去优化~~o.0~~

动态规划入门2（LCS模板）_c++ lcs模版