[动态规划](2)线性DP

数字三角形

引言:

所谓线性DP,是咱们的递推方程,有一个明显的线性关系,他可能是一维线性,也可能是二维线性的

模板题:898. 数字三角形 - AcWing题库

image-20210706163435958

思维导图:

```C++ 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

转换为:

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5


![image-20210706185501876](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210706185501876.png)

代码:

```C++
//取所有能走到f[i][j]路径的最大值,依照题意,f[i][j]状态可由其左上和右上转移过来
//左上既是f[i-1][j-1],右上既是f[i-1][j]
//既可得出状态转移方程为:f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1010;//数据范围
const int INF = 0x3f3f3f3f;//极小值
int n;//数字三角形层数
int a[N][N], f[N][N];//a数组存储数字三角形,f数组存储状态转移

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);

    //初始化状态转移数组,由于每行最后一个数可以由其右上转移过来,所以需要初始化边界+1
    for (int i = 1; i <= n; i++)//行不用
        for (int j = 0; j <= i + 1; j++)//对照数字三角形图即可理解
            f[i][j] = -INF;

    //进行状态转移
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;
    for (int i = 1; i <= n; i++) res = max(f[n][i], res);
    cout << res << endl;
    return 0;
}

最长上升子序列

模板题:895. 最长上升子序列 - AcWing题库

image-20210706210831836

思维导图:

image-20210706205814703

代码

```C++ //n²的时间复杂度,在所有上升子序列中选取最长的序列长度 //则可以定义所有以 a[i] 结尾的 子序列 中 最长的上升子序列 //若在a[i]之前出现元素a[j]比a[i]小,则a[j]+1与a[i]作比较

include

using namespace std; const int N = 1010; int a[N],f[N]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=1;i<=n;i++){
    f[i]=1;//全部初始化为1,代表以自身结尾,只包含自身一个元素
    for(int j=1;j<=i;j++)
        if(a[j]<a[i]) //若出现a[j]<a[i],则可添加a[j]所在子序列长度加上a[i],与当前以i结尾最长子序列长度选取max
            f[i] = max(f[i],f[j]+1);
}

int res=-0x3f3f3f3f;

for(int i=1;i<=n;i++) res=max(res,f[i]);
cout<<res<<endl;

return 0;

}


#### 二分优化

**模板题:[896. 最长上升子序列 II - AcWing题库](https://www.acwing.com/problem/content/898/)**

思路:

- 基于 朴素算法 的单调性:**找到一个最大的小于等于当前数的数**,我们可以用 **二分** 来优化,我们利用二分找到最后一个小于它的数 j,然后去判断以 j 结尾的子序列长度 + 1 是否大于 i 

#### 代码:

```C++
#include<iostream>
using namespace std;
const int N =100010;
int a[N],f[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    f[0]=-0x3f3f3f3f;//长度为0的数是0x3f,作为哨兵

    int len=0;//最大长度
    for(int i=1;i<=n;i++){
        int l=0,r=len;
        while(l<r){//利用二分去在当前长度区间找寻最后一个小于它的数
            int mid = l+r+1>>1;
            if(f[mid] >= a[i]) r=mid-1;
            else l=mid;
        }
        len=max(len,r+1);
        f[r+1]=a[i];//更新当前长度的结尾数字
    }
    cout<<len<<endl;
    return 0;
}

/*
q[r + 1] = a[i];这里并没有选择最小的是因为可以保证“相等长度的上升序列,
后来得到的序列的结尾数值一定小于或等于前面得到的”,假设先前得到的序列xxxa,
后来得到的序列xxxb,a和b满足b在a的后面且b>a,
那么显然xxxb一定不是以b结尾的最长上升子序列,正确序列中一定包含a,
所以假设不成立,命题得证。
*/

最长公共子序列

模板题:897. 最长公共子序列 - AcWing题库

image-20210706222042350

思维导图:

image-20210706225223320

代码

```c++ //状态表示:所有在第一个序列的前i个字母中出现.且在第二个序列的前j个字母中出现的最大值

include

include

using namespace std; const int N = 1010; int n,m; char a[N],b[N]; int f[N][N]; int main(){ scanf("%d %d",&n,&m); cin>>a>>b;

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1]);
            //选a的第i个字母和选b的第j个字母的最大值
        if(a[i-1]==b[j-1]) 
            f[i][j] = max(f[i][j],f[i-1][j-1]+1);
                //当两个字母相等时,选取这个字母与不选这个字母的最大值
    }        
}

cout<<f[n][m]<<endl;
return 0;

}


#### 最短编辑距离

**模板题:[902. 最短编辑距离 - AcWing题库](https://www.acwing.com/problem/content/904/)**

![image-20210706225816594](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210706225816594.png)

#### 思维导图:

![image-20210707003333190](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210707003333190.png)

#### 代码:

```C++
//状态表示:所有将a[1 - i]变换到b[1 - j]的最小值
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;
int main() {
    cin >> n >> a;
    cin >> m >> b;

    for (int i = 0; i <= m; i++) f[0][i] = i;//将a的前0个字母变换到b[1-m]个字母,只有增一种操作
    for (int i = 0; i <= n; i++) f[i][0] = i;//将a[1 - n]个字母变换到b的前0个字母,只有删一种操作

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            //当a的前i-1个字母与b的前j个字母相等时,“增” 一种操作
            //当a的前i个字母与b的前j-1个字母相等时,“删” 一种操作
            if (a[i - 1] == b[j - 1]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); //当a的第i个字母与b的第j个字母相等时,不需要操作
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);//当a的第i个字母与b的第j个字母不相等时,进行 “改” 操作
        }

    cout << f[n][m] << endl;
    return 0;
}

本文链接:

https://nullcode.fun/151.html
1 + 9 =
快来做第一个评论的人吧~