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

数字三角形

引言:

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

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

image-20210706163435958

思维导图:

        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

代码:

//取所有能走到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

代码

//n²的时间复杂度,在所有上升子序列中选取最长的序列长度
//则可以定义所有以 a[i] 结尾的 子序列 中 最长的上升子序列
//若在a[i]之前出现元素a[j]比a[i]小,则a[j]+1与a[i]作比较
#include<iostream>
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题库

思路:

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

代码:

#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

代码

//状态表示:所有在第一个序列的前i个字母中出现.且在第二个序列的前j个字母中出现的最大值
#include<iostream>
#include<algorithm>
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题库

image-20210706225816594

思维导图:

image-20210707003333190

代码:

//状态表示:所有将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 + 4 =
快来做第一个评论的人吧~