关于二维DP————站上巨人的肩膀

42 阅读 0 评论 28 点赞

我是靠谱客的博主酷酷鸵鸟，最近开发中收集的这篇文章主要介绍关于二维DP————站上巨人的肩膀，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Python微信订餐小程序课程视频

https://edu.csdn.net/course/detail/36074

Python实战量化交易理财系统

https://edu.csdn.net/course/detail/35475
意匠惨淡经营中ing，

语不惊人死不休…

前几天学了DP，做了个简单的整理，记录了关于DP的一些概念之类的，今天记录一下刚学的一个类型

————关于二维DP

那建立二维数组主要是干嘛用的呢？？？其实就是是记录两个状态，（我也不是很清楚），然后再递推

直接上题吧

T1 、最长公共子序列：

好像有印象，之前做过一道类似的题，叫做最长上升子串，需要注意的是，这俩可不是很一样，人家子序列可以不连续，只要是相对顺序不改变就行，但是子串必须是连续的，针对这种题，我们联想起原来做题时想的状态转移方程，再加以改动就可以了：

f[i][j] 还是表示数组a的前i个元素和b数组的前j个元素能组成的最长子串的长度

那很容易以相同的方法联想到子序列，还是分情况讨论：

1、x[i]==y[j]时：f[i][j]=f[i-1][j-1]+1 （就是它们如果相等，长度就是不加上它们时组成的子串的长+1）

2、x[i]!=y[j]时：

1 2 3 4 5 和 2 3 5，这两个子串在 i=4,j=2 的时候，由于a[i]!=b[j]，加上它们俩和不加他们俩其实并不影响最长长度，所以i和j对应的他们以前这些元素（不包括i，j）能组成的最长长度其实和它们现在（包括i，j）能组成的长度是相同的（不必+1），所以当a[i]!=b[j]，它们对应的长度可以是f[i-1][j],也可以是f[i][j-1],取个max就好

再考虑边界，当一个字符串有0个元素时，它们的f[i][j]永远是0，所以f[0][j]=0 ，f[i][0]=0。

代码如下：

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 int f[1001][1001];
 7 char x[1001],y[1001];
 8 int maxn;
 9 int main()
10 {
11 cin>>x;
12 cin>>y;
13 int m=strlen(x);
14 int n=strlen(y);
15 for(int i=0;i)
16 for(int j=0;j)
17  {
18 f[i][0]=0;
19 f[0][j]=0;
20  }
21 for(int i=1;i<=m;i++)
22  {
23 for(int j=1;j<=n;j++)
24  {
25 if(x[i-1]==y[j-1]) f[i][j]=f[i-1][j-1]+1;//人家是从0开始纳入的，所以这里要－1
26 else f[i][j]=max(f[i-1][j],f[i][j-1]);
27 maxn=maxn>f[i][j]? maxn:f[i][j]; 
28  }
29  } 
30 printf("%d",maxn);
31 return 0;
32 }

T2、编辑距离：

题意：有两个字符串，现在有三种操作：1、删除一个字符，2、插入一个字符，3、将一个字符改成另一个字符，现在要求要么花最少的字符操作次数，将字符串A转成B（只能操作A串）。

还是先设变量，f[i][j]表示把x[1_i]变为y[ij]的最少操作次数，现在的目标就是求出状态转移方程：

还还还是分两种情况讨论：

当 x[i]==y[j] 时，那我们就可以不对它们进行操作了，也就是说我们直接让f[i][j]=f[i-1][j-1]

当 **x[i]!=y[j]**时，我们有三种操作，需要分别求出他们的状态转移方程

1、删除 x[i]，那就是上一次的操作次数再加上1，即 f[i][j]=f[i-1][j]+1

2、给x[i]插入新字符：那就是相当于给y[j]删去一位，即 f[i][j]=f[i][j-1]+1

3、将x[i]变为y[j]：目前a数组的前i位和b数组的前j